题目描述

给一颗 $n$ 个节点的树，初始时 $1$ 号节点被染黑，其余是白的。两个人轮流操作，一开始 B 在 $1$ 号节点。每一轮，A 选择 $k$ 个点染黑，然后 B 走到一个相邻节点，如果 B 当前处于白点则 B 胜，否则当 A 将所有点染为黑点时 A 胜。求能让 A 获胜的最小的 $k$。

输入格式

第一行读入一个整数 $n$，表示树的节点数

接下来 $n$ 行，每行读入两个用空格分隔的整数 $u,v$，表示 $u$、$v$ 之间有一条边。

输出格式

输出仅有一行，表示让 A 获胜的最小的 $k$。

7
1 2
1 3
2 5
2 6
7 2
4 1

3

提示

$n \le 3 \times 10^5$。