8319번 - Termites 2 다국어

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 n vertices and n-1 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 (e₁, e₂, ..., e_n-1) of the edges of the tree they are going to eat. The game will last at most n-1 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 kth round the playing termite must choose an uneaten end of edge e_k and eat it. If both ends of e_k are eaten before the termite makes its move, the game ends with its loss. If the game does not end in n-1 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.

In the first line of the standard input there is an integer n (2 ≤ n ≤ 500,000) - the number of vertices of the tree. In the next n-1 lines given are the tree's edges in the order set by the termites. In the ith of these lines there are two integers u_i and v_i (1 ≤ u_i, v_i ≤ n) - the indices of the ends of edge e_i.

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 -1 if the game will end with a draw.

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