F. Nimesweeper!
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alexander and Babin live on an abandoned island. Their only entertainment consists of trees, stones, and bombs (don't ask where they came from). They are very bored and want to play a game. Alexander suggested playing "Minesweeper", while Babin suggested "Nim". As a compromise, they decided to play Nimesweeper!

With no other choice, the guys chose a tree as the game board. Recall that a tree is a connected undirected graph without cycles.

In the course of the overall game, Alexander starts playing the subgame "Minesweeper". Initially, none of the vertices of the tree contain bombs. On his turn, Alexander chooses any vertex without a bomb and places a bomb in it. After that, in each vertex that does not contain a bomb, a number of stones equal to the number of bombs in its neighboring vertices is placed.

Babin can interrupt Alexander after any of his moves. Once this happens, they start playing "Nim" with the resulting piles of stones, with Babin going first.

If Babin does not interrupt Alexander, Alexander makes the next move (places another bomb), after which the piles of stones are updated, and so on, until Babin starts the game of "Nim".

The player who cannot make a move in "Nim" loses.

Babin really wants to win, so he will interrupt Alexander at the earliest possible moment when he can guarantee his victory.

Alexander, well aware that he cannot win this game, decided instead to maximize his enjoyment, so he wants to place as many bombs as possible before Babin starts the game of "Nim". Please help Alexander find the maximum number of bombs he can place!

Recall that in the game of "Nim", the first player wins if and only if the bitwise XOR of the sizes of the piles is non-zero.

Recall that XOR or Exclusive OR is a binary operation that is applied to each pair of bits in the same position in the binary representations of numbers such that the result at that position is 0 if the bits are equal, and 1 otherwise. For example, 3 XOR 5 = 6, since $$$3_{10}$$$ = $$$011_2$$$, $$$5_{10}$$$ = $$$101_2$$$, and therefore after applying the operation, the second and third bits become equal to 1, while the first bit becomes 0, resulting in $$$110_2$$$ = $$$6_{10}$$$.

Input

The first line of the input contains a single integer $$$n$$$ ($$$2 \leq n \leq 369$$$) — the number of vertices in the tree.

The following $$$n - 1$$$ lines contain pairs of integers $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — the edges of the tree. It is guaranteed that these edges indeed form a tree.

Output

In a single line, output a single number — the maximum number of bombs that can be placed.

Scoring
GroupPointsAdditional Constraints Required Groups
18$$$n \le 8$$$–
211$$$n \le 18$$$1
320$$$n \le 45$$$1–2
419$$$n \leq 128$$$1–3
518$$$n \leq 243$$$1–4
620Degrees of all vertices $$$\le 3$$$–
74–1–6
Examples
Input
3
1 2
1 3
Output
2
Input
9
1 2
2 3
3 4
4 5
5 6
6 7
5 8
8 9
Output
5
Input
13
7 6
7 5
7 4
7 3
7 2
7 1
1 12
2 11
3 10
4 9
5 8
6 13
Output
8