Cut 'em all!

Description:

Input:

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) denoting the size of the tree.

The next $$$n - 1$$$ lines contain two integers $$$u$$$, $$$v$$$ ($$$1 \le u, v \le n$$$) each, describing the vertices connected by the $$$i$$$-th edge.

It's guaranteed that the given edges form a tree.

Output:

Output a single integer $$$k$$$ — the maximum number of edges that can be removed to leave all connected components with even size, or $$$-1$$$ if it is impossible to remove edges in order to satisfy this property.

Sample Input:

4
2 4
4 1
3 1

Sample Output:

1

Sample Input:

3
1 2
1 3

Sample Output:

-1

Sample Input:

10
7 1
8 4
8 10
4 7
6 5
9 3
3 5
2 10
2 5

Sample Output:

4

Sample Input:

2
1 2

Sample Output:

0

Note:

In the first example you can remove the edge between vertices $$$1$$$ and $$$4$$$. The graph after that will have two connected components with two vertices in each.

In the second example you can't remove edges in such a way that all components have even number of vertices, so the answer is $$$-1$$$.