题目描述

$N$ 頂点の木があります。 頂点には $0$ から $N\ -\ 1$ まで番号が振られています。 また、$i$ ($0\ <\ =\ i\ <\ N\ -\ 1$) 番目の辺は頂点 $a_i$ と $b_i$ を結んでいます。 各頂点対 $u$, $v$ ($0\ <\ =\ u,\ v\ <\ N$) に対して、距離 $d(u,\ v)$ を「パス $u$-$v$ に含まれる辺の本数」と定義します。

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

まず、アンテナの個数 $K$ ($1\ <\ =\ K\ <\ =\ N$) を自由に決めます。 そして、すべて相異なる $K$ 個の頂点 $x_0$, $x_1$, ..., $x_{K\ -\ 1}$ を自由に選び、各頂点にアンテナ $0$, $1$, ..., $K\ -\ 1$ を設置します。 頂点 $v$ に宇宙人が襲来すると、アンテナ $k$ ($0\ <\ =\ k\ <\ K$) は距離 $d(x_k,\ v)$ を出力します。 すぬけ君は、これら $K$ 個の出力結果をもとに、宇宙人が襲来した頂点を特定します。 よって、どの頂点に宇宙人が襲来してもその頂点を一意に特定するためには、次の条件が成り立つ必要があります。

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

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

输入格式

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

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

输出格式

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

题目大意

有一棵 $n$ 个节点的树，无边权。

选择 $k$ 个点。树上每个点到这 $k$ 个点的距离构成一个 $k$ 维坐标。

求得最小的 $k$ 使得每个坐标都不相同。

5
0 1
0 2
0 3
3 4

2

2
0 1

1

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

3

提示

制約

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

Sample Explanation 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)$

Sample Explanation 2

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

Sample Explanation 3

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