题目描述

给定一棵包含 $N$ 个顶点的树，顶点编号为 1、2、……、$N$ 。其中第 $i$ 条边（$1≤i<N$）连接顶点 $u_i$ 和顶点 $v_i$。

考虑重复执行若干次以下操作： 选择一个叶节点 $v$，将其与所有关联的边一并删除。 请找出删除顶点 1 所需的最少操作次数。

输入格式

输入通过标准输入按以下格式给出：

• N
• $u_1$ $v_1$
• $u_2$ $v_2$

⋮

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

输出格式

在一行中输出答案。

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

5

给定的图结构如下：

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

顶点 1 无法通过 4 次或更少的操作被删除，因此输出 5。

6
1 2
2 3
2 4
3 5
3 6

1

在给定的图中，顶点 1 是叶节点。因此，你可以在第一次操作中就选择并删除顶点 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

数据规模与约定

• $2≤N≤3×10^5$
• $1≤u_i<v_i≤N$（$1≤i<N$）
• 给定的图是一棵树
• 所有输入值均为整数