Termites 2

Memory limit: 128 MB

Do you still remember the two friendly plank-eating termites which never grow tired of mental exercise? After eating away most of the fences in Byteland, they have got an appetite for trees.

A tree is a connected undirected graph with vertices and edges. Our two termites quickly got bored with monotonously eating the vertices - to make their meal more interesting, they have invented a game. They agreed on an ordering of the edges of the tree they are going to eat. The game will last at most rounds, with exactly one termite making a move in each round. The players move alternately (the starting one plays in round 1, the second one in round 2, in round 3 again the first one, and so on). In the th round the playing termite must choose an uneaten end of edge and eat it. If both ends of are eaten before the termite makes its move, the game ends with its loss. If the game does not end in rounds, it is tied.

We assume that the termites (after all, experienced in this kind of games) play errorlessly and the termite which has a winning strategy wants to win in the earliest possible round, while its enemy tries to delay its defeat for as long as it can. Your task is to determine, for a given tree and the ordering of its edges set by the termites, the round that the game will end in.

Input

In the first line of the standard input there is an integer () - the number of vertices of the tree. In the next lines given are the tree's edges in the order set by the termites. In the th of these lines there are two integers and () - the indices of the ends of edge .

Output

In the first and only line of the standard output exactly one integer should be written - the number of the round in which the game will end, or if the game will end with a draw.

Example

For the input data:

5
2 3
1 2
4 5
3 4

the correct result is:

4

Explanation of the example: If in the first round the starting termite eats vertex and in the third round it eats vertex , its opponent will not have any valid moves in the fourth round, regardless of its play in the second round.

Task author: Jakub Pachocki.