题目描述

The king of Byteotia, Byteasar, is returning to his country after a victorious battle.

In Byteotia, there are towns connected with only roads.

It is known that every town can be reached from every other town by a unique route, consisting of one or more (direct) roads.

(In other words, the road network forms a tree).

The king has just entered the capital.

Therein a triumphal arch, i.e., a gate a victorious king rides through, has been erected.

Byteasar, delighted by a warm welcome by his subjects, has planned a triumphal procession to visit all the towns of Byteotia, starting with the capital he is currently in.

The other towns are not ready to greet their king just yet - the constructions of the triumphal arches in those towns did not even begin!

But Byteasar's trusted advisor is seeing to the issue.

He desires to hire a number of construction crews.

Every crew can construct a single arch each day, in any town.

Unfortunately, no one knows the order in which the king will visit the towns.

The only thing that is clear is that every day the king will travel from the city he is currently in to a neighboring one.

The king may visit any town an arbitrary number of times (but as he is not vain, one arch in each town will suffice).

Byteasar's advisor has to pay each crew the same flat fee, regardless of how many arches this crew builds.

Thus, while he needs to ensure that every town has an arch when it is visited by the king, he wants to hire as few crews as possible.

Help him out by writing a program that will determine the minimum number of crews that allow a timely delivery of the arches.

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

输入格式

The first line of the standard input contains a single integer (), the number of towns in Byteotia.

The towns are numbered from 1 to , where the number 1 corresponds to the capital.

The road network is described in lines that then follow.

Each of those lines contains two integers, (), separated by a single space, indicating that towns and are directly connected with a two way road.

In tests worth 50% of the total points, an additional condition holds.

输出格式

The first and only line of the standard output is to hold a single integer, the minimum number of crews that Byteasar's advisor needs to hire.

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

3

提示

给一颗树，1号节点已经被染黑，其余是白的，两个人轮流操作，一开始B在1号节点，A选择k个点染黑，然后B走一步，如果B能走到A没染的节点则B胜，否则当A染完全部的点时，A胜。求能让A获胜的最小的k