题面描述

给定一颗 $n$ 个节点的无根树。每次你可以删除一个叶子节点（即度数为 $1$ 的点），问最少多少次操作可以删除 $1$ 节点。

$2 \le n \le 3 \times 10^5$。

题目描述

输入格式

按照下面的形式输入

$N$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_{N-1}$ $v _{N-1}$

输出格式

输出答案

样例 #1

样例输入 #1

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

样例输出 #1

5

样例 #2

样例输入 #2

6
1 2
2 3
2 4
3 5
3 6

样例输出 #2

1

样例 #3

样例输入 #3

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

样例输出 #3

12

提示

制約

• $2\leq\ N\leq3\times10^5$
• $ 1\leq\ u\ _\ i\lt\ v\ _\ i\leq\ N\ (1\leq\ i\lt\ N) $

Sample Explanation 1

给定的图表如下： 通过选择顶点$9,8,7,6,1$进行操作，可以在$5$次操作中删除顶点$1$。 $4$次以下操作不能删除顶点$1$，因此请输出$5$。

Sample Explanation 2

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