配点 : $900$ 点

問題文

$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$ に含まれる辺の本数」と定義します。

近い将来、いずれか $1$ 個の頂点に宇宙人が襲来することが予想されています。 すぬけ君は、宇宙人が襲来したときにその頂点をすぐに特定したいと考えています。 そのために、あらかじめいくつかの頂点にアンテナを設置しておくことにしました。

まず、アンテナの個数 $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)$ を出力します。 すぬけ君は、これら $K$ 個の出力結果をもとに、宇宙人が襲来した頂点を特定します。 よって、どの頂点に宇宙人が襲来してもその頂点を一意に特定するためには、次の条件が成り立つ必要があります。

• 各頂点 $u$ ($0 \leq u < N$) に対してベクトル $(d(x_0, u), ..., d(x_{K - 1}, u))$ を考えたとき、これら $N$ 通りのベクトルはすべて相異なる。

条件を満たすようにアンテナを設置するとき、アンテナの個数 $K$ の最小値を求めてください。

制約

• $2 \leq N \leq 10^5$
• $0 \leq a_i, b_i < N$
• 与えられるグラフは木である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_0$ $b_0$

$a_1$ $b_1$

$:$

$a_{N - 2}$ $b_{N - 2}$

出力

条件を満たすようにアンテナを設置するとき、アンテナの個数 $K$ の最小値を出力せよ。

5
0 1
0 2
0 3
3 4

2

例えば、頂点 $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 1

1

例えば、頂点 $0$ にアンテナを設置すればよいです。

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

3

例えば、頂点 $0$, $4$, $9$ にアンテナを設置すればよいです。