题目描述

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

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

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

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

• 什么是树？树是一种无向图，它是连通的且没有环。
• 什么是叶子？树中的叶子是指度数最多为$1$ 的顶点。

输入格式

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

$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

说明/提示

样例 1 解释

给定的图如下所示：

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

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

样例 2 解释

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

数据范围

• $2\leq\ N\leq3\times10^5$
• $ 1\leq\ u\ _\ i\lt\ v\ _\ i\leq\ N\ (1\leq\ i\lt\ N) $
• 给定的图是一棵树
• 所有输入值都是整数。