给定一棵有 $N$ 个顶点的树。顶点编号为 $0$ 到 $N-1$，第 $i$ 条边（$0 \le i < N-1$）连接顶点 $a_i$ 和 $b_i$。对于每一对顶点 $u$ 和 $v$（$0 \le u, v < N$），我们定义 $d(u, v)$ 为路径 $u-v$ 上的边数。

预计会有外星人入侵其中一个顶点。Snuke 希望在入侵发生时立即识别出该顶点。为此，他决定在某些顶点上安装天线。

首先，他决定天线的数量 $K$（$1 \le K \le N$）。然后，他选择 $K$ 个不同的顶点 $x_0, x_1, \dots, x_{K-1}$，并分别在这些顶点上安装天线 $0, 1, \dots, K-1$。如果顶点 $v$ 被外星人入侵，天线 $k$（$0 \le k < K$）将输出距离 $d(x_k, v)$。基于这 $K$ 个输出，Snuke 将识别出被入侵的顶点。因此，为了无论哪个顶点被入侵都能识别出该顶点，必须满足以下条件：对于每个顶点 $u$（$0 \le u < N$），考虑向量 $(d(x_0, u), \dots, d(x_{K-1}, u))$。这 $N$ 个向量必须互不相同。

求满足该条件时天线数量 $K$ 的最小值。

输入格式

输入按以下格式给出：

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

数据范围

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

输出格式

输出满足条件时天线数量 $K$ 的最小值。

样例

样例输入 1

5
0 1
0 2
0 3
3 4

样例输出 1

2

样例输入 2

2
0 1

样例输出 2

1

样例输入 3

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

样例输出 3

3

说明

在样例 1 中，在顶点 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 中，一种可能的解是在顶点 0 上安装天线。

在样例 3 中，一种可能的解是在顶点 0, 4, 9 上安装天线。