AT_apc001_e Antennas on Tree

有一棵包含 $N$ 个顶点的树。顶点编号为 $0$ 到 $N-1$。对于每一条边 $i$（$0 \leq i < N-1$），它连接着顶点 $a_i$ 和 $b_i$。对于每一对顶点 $u, v$（$0 \leq u, v < N$），我们将距离 $d(u, v)$ 定义为 $u$ 到 $v$ 的路径上经过的边的数量。 在不久的将来，预计会有宇宙人袭击其中一个顶点。SunuKe 君希望，在宇宙人袭击时能够立即确定被袭击的顶点。为此，他打算提前在树上的若干顶点安装天线。 首先，可以自由选择天线的个数 $K$（$1 \leq K \leq N$）。然后可以自由选择 $K$ 个各不相同的顶点 $x_0, x_1, ..., x_{K-1}$，并分别在每个顶点上安装天线 $0, 1, ..., K-1$。当某顶点 $v$ 被宇宙人袭击时，第 $k$ 个天线（$0 \leq k < K$）会输出 $d(x_k, v)$。SunuKe 君通过这 $K$ 个输出值，试图唯一确定被袭击的顶点。因此，为使无论哪个顶点被宇宙人袭击时都能唯一确定该顶点，需满足以下条件： - 对于每个顶点 $u$（$0 \leq u < N$），设向量为 $(d(x_0, u), ..., d(x_{K-1}, u))$，则这 $N$ 个向量必须完全不同。 请你求出，满足条件时，所需天线的最小个数 $K$。

输入以如下格式从标准输入读入： > $N$ $a_0$ $b_0$ $a_1$ $b_1$ $\dots$ $a_{N-2}$ $b_{N-2}$

输出满足条件所需的最少天线数量 $K$。

### 限制条件 - $2 \leq N \leq 10^5$ - $0 \leq a_i, b_i < N$ - 给定的图保证是一棵树。 ### 样例说明 1 例如，可以在顶点 $1$、$3$ 安装天线。此时，以下 $5$ 个向量均不相同： - $(d(1, 0), d(3, 0)) = (1, 1)$ - $(d(1, 1), d(3, 1)) = (0, 2)$ - $(d(1, 2), d(3, 2)) = (2, 2)$ - $(d(1, 3), d(3, 3)) = (2, 0)$ - $(d(1, 4), d(3, 4)) = (3, 1)$ ### 样例说明 2 例如，可以只在顶点 $0$ 安装一个天线。 ### 样例说明 3 例如，可以在顶点 $0$、$4$、$9$ 安装天线。 由 ChatGPT 5 翻译