Cut

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

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

Hint

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

Source

ftiasch

Manager

Information
Solved Number47
Submit Number76
Problem Tags
dfs and similar
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel