删除叶子

题目描述

给定一棵有 $N$ 个顶点的树:顶点 $1$,顶点 $2$,$\ldots$,顶点 $N$。 第 $i$ 条边 $(1\leq i\lt N)$ 连接顶点 $u _ i$ 与顶点 $v _ i$。

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

选择一个叶子顶点 $v$,将其连同所有关联的边一起删除。

求删除顶点 $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

给定的图如下所示。

例如,可以按 $9,8,7,6,1$ 的顺序选择顶点,用 5 次操作删除顶点 1。

无法在 4 次或更少的操作中删除顶点 1,因此输出 5。

6
1 2
2 3
2 4
3 5
3 6

1

在给定的图中,顶点 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\leq N\leq3\times10^5$
• $1\leq u _ i\lt v _ i\leq N\ (1\leq i\lt N)$
• 给定的图是一棵树。
• 输入中的所有值均为整数。

提示

什么是树? 树是不含环的连通无向图。

什么是叶子? 树中度至多为 $1$ 的顶点称为叶子。