问题描述

给定一棵包含 $N$ 个顶点的树。这些顶点从 $0$ 到 $N-1$ 进行编号，第 $i$ 条边 ($0 ≤ i < N - 1$) 连接了顶点 $a_i$ 和 $b_i$。对于每一对顶点 $u$ 和 $v$ ($0 ≤ u, v < N$)，我们定义距离 $d(u, v)$ 为路径 $u$-$v$ 上的边的数量。

预计某个顶点将被外星人入侵。当入侵发生时，Snuke 希望立即确定哪个顶点被入侵。为了做到这一点，他决定在某些顶点上安装天线。

首先，他决定天线的数量 $K$ ($1 ≤ K ≤ N$)。然后，他选择 $K$ 个不同的顶点，在其上分别安装天线 $0$、$1$、...、$K - 1$。如果顶点 $v$ 被外星人入侵，天线 $k$ ($0 ≤ k < K$) 将输出距离 $d(x_k, v)$。基于这 $K$ 个输出，Snuke 将确定被入侵的顶点。因此，为了无论哪个顶点被入侵都能够确定被入侵的顶点，必须满足以下条件：

• 对于每个顶点 $u$ ($0 ≤ u < N$)，考虑向量 $(d(x_0, u), ..., d(x_{K - 1}, u))$。这些 $N$ 个向量是不同的。

找到满足条件时 $K$ 的最小值，即天线的数量。

约束条件

• $2 ≤ N ≤ 10^5$
• $0 ≤ a_i, b_i < N$
• 给定的图是一棵树。

输入

输入以以下格式从标准输入给出：

$N$ $a_0$ $b_0$ $a_1$ $b_1$ $:$ $a_{N - 2}$ $b_{N - 2}$

输出

在满足条件时，打印天线数量 $K$ 的最小值。

示例输入 1

5
0 1
0 2
0 3
3 4

示例输出 1

2

例如，在顶点 $1$ 和 $3$ 上安装天线。然后，以下五个向量是不同的：

• $(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

2
0 1

示例输出 2

1

例如，在顶点 $0$ 上安装天线。

示例输入 3

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

示例输出 3

3

例如，在顶点 $0$、$4$、$9$ 上安装天线。