Cut 'em all!
Description
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$ ($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 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.
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.
4<br>2 4<br>4 1<br>3 1<br>
3<br>1 2<br>1 3<br>
10<br>7 1<br>8 4<br>8 10<br>4 7<br>6 5<br>9 3<br>3 5<br>2 10<br>2 5<br>
2<br>1 2<br>
1
-1
4
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$.