题目描述

有一棵包含 $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$。

输入输出样例 #1

输入 #1

5
0 1
0 2
0 3
3 4

输出 #1

2

输入输出样例 #2

输入 #2

2
0 1

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

3

说明/提示

限制条件

• $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$ 安装天线。