AT_abc333_d.[ABC333D] Erase Leaves

给定一棵包含 $N$ 个顶点的树，顶点编号为 $1, 2, \ldots, N$。第 $i$ 条边 $(1 \leq i < N)$ 连接顶点 $u_i$ 和 $v_i$。

你可以重复进行如下操作任意次：

• 选择一个叶子顶点 $v$，将顶点 $v$ 及其所有连接的边删除。

请你求出，最少需要进行多少次操作才能删除顶点 $1$。

什么是树？树是指无向图中连通且无环的图。详细内容请参考：Wikipedia「木 (数学)」。

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

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

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

请输出答案，输出一行。

限制条件

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq u_i < v_i \leq N\ (1 \leq i < N)$
• 给定的图为树
• 输入均为整数

样例解释 1

给定的图如下所示。

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

无法在 $4$ 次或更少的操作内删除顶点 $1$，因此应输出 $5$。

样例解释 2

在给定的图中，顶点 $1$ 是叶子。因此，在第 $1$ 次操作时即可选择顶点 $1$ 并将其删除。

由 ChatGPT 4.1 翻译