题目描述

给定一棵 $n$ 个节点的树。初始时 $1$ 号节点被涂成黑色，其余节点都是白色。小蓝与小灰轮流操作，游戏开始时棋子位于 $1$ 号节点。

每一轮，小蓝先选择 $k$ 个白色节点涂成黑色，然后小灰把棋子移到一个相邻节点。如果移动后棋子停在一个白色节点上，小灰获胜；如果某一时刻所有节点都被涂成了黑色，小蓝获胜。

请你求出：能让小蓝必胜的最小的 $k$。

输入格式

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

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

输出格式

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

样例

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

3

提示

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