Cut 'em all!

You're given a tree with n vertices.

Your task is to determine the maximum possible number of edges that can be removed in such a way that all the remaining connected components will have even size.

The first line contains an integer n$n$ (1≤n≤105) denoting the size of the tree.

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

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

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

4
2 4
4 1
3 1

1

3
1 2
1 3

-1

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

4

2
1 2

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$$$.