题目描述

给定一棵有$N$个顶点的树：顶点1、顶点2、...、顶点$N$。第$i$条边$(1 ≤ i < N)$连接顶点$u_i$和$v_i$。

考虑重复执行以下操作若干次：

• 选择一个叶子顶点$v$并删除它以及所有与之相连的边。

找出删除顶点1所需的最少操作次数。

• 什么是树？树是一种无向图，它是连通的且没有环。

• 什么是叶子？树中的叶子是指度数最多为1的顶点。

输入格式

输入从标准输入中以下列格式给出：

$N$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_{N-1}$ $v_{N-1}$

输出格式

输出所求答案。

样例

9
1 2
2 3
2 4
2 5
1 6
6 7
7 8
7 9

5

6
1 2
2 3
2 4
3 5
3 6

1

24
3 6
7 17
7 20
7 11
14 18
17 21
6 19
5 22
9 24
11 14
6 23
8 17
9 12
4 17
2 15
1 17
3 9
10 16
7 13
2 16
1 16
5 7
1 3

12

样例解释

【样例1说明】

给定的图如下所示：

例如，你可以按9、8、7、6、1的顺序选择顶点，通过五次操作删除顶点1。

顶点1无法通过四次或更少的操作删除，所以输出5。

【样例2说明】

在给定的图中，顶点1是一个叶子。因此，你可以在第一次操作中选择并删除顶点1。

数据范围

• $2 ≤ N ≤ 3 × 10^5$
• $1 ≤ u_i < v_i ≤ N (1 ≤ i < N)$
• 给定的图是一棵树
• 所有输入值都是整数。

来源

• AtCoder ABC333D