Cut

Cut(in another word, remove) edges the given tree $$T$$ so that each connected component has even number of nodes.

Find out the maximum number of removed edges.

Input

The first line contains one integer $$n$$, which denotes the number of nodes of tree $$T$$.

The following $$(n - 1)$$ lines with two integers $$a_i, b_i$$, which denotes edge $$(a_i, b_i)$$.

Note that the nodes are labled by $$1, 2, \ldots, n$$.

($$1 \leq n \leq 10^5$$, $$n$$ is even)

Output

The only integer shows the maximum number of removed edges.

Sample input

4
1 2
2 3
3 4

Sample output

1

Note

Only edge $$(2, 3)$$ can be removed.

Source

Contest #3 on acdream oj by ftiasch