题目描述

给定由顶点 $1, 2, \ldots, N$ 的 $N$ 个顶点组成的树。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

考虑以下操作，可以任意重复多次：

• 选择一个叶子顶点 $v$，删除顶点 $v$ 及与之相连的边。

请计算至少需要进行多少次操作才能删除顶点 $1$。

什么是树？树是一种无向图，它是连通的且没有回路。

什么是叶子？树的叶子是指度数不超过 $1$ 的顶点。

输入格式

第一行一个整数$N$，表示节点数量。

接下来$N-1$行，每行两个整数，表示一条边。

输出格式

输出答案，只有一行。

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

5

6
1 2
2 3
2 4
3 5
3 6

1

提示

约束条件

• $2 \le N \le 3 \times 10^5$
• $1 \le u_i < v_i \le N\ (1 \le i < N)$
• 给定的图是一棵树
• 输入都是整数