问题描述

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

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

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

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

输入格式

第一行一个整数 $N$，表示顶点数；

接下来的 $N-1$ 行，每行空格隔开的两个整数$u_i,v_i$,表示两者之间有一条边。

输出格式

在单独的一行中输出答案。

样例输入 1

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

样例输出 1

5

给定的图如下所示：

例如，你可以按顺序选择顶点 $9,8,7,6,1$，在五次操作中删除顶点 $1$。

顶点 $1$ 无法在四次或更少的操作中被删除，因此输出 $5$。

样例输入 2

6
1 2
2 3
2 4
3 5
3 6

样例输出 2

1

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

样例输入 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)$

• 给定的图是一棵树。