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