## Algorithm

C. Cut 'em all!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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

The next n1�−1 lines contain two integers uv (1u,vn1≤�,�≤�) 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−1 if it is impossible to remove edges in order to satisfy this property.

Examples
input
Copy
42 44 13 1
output
Copy
1
input
Copy
31 21 3
output
Copy
-1
input
Copy
107 18 48 104 76 59 33 52 102 5
output
Copy
4
input
Copy
21 2
output
Copy
0
Note

In the first example you can remove the edge between vertices 11 and 44. 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−1.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1e5 + 1;
int n, res;
bool vis[N];
vector<vector<int> > g;

int DFS(int u) {
vis[u] = true;

bool ok = false;
int ret = 1;
for(int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];

if(!vis[v]) {
int tmp = DFS(v);
if(tmp % 2 == 0)
++res;
ret += tmp;
}
}

return ret;
}

int main() {
cin >> n;
g.resize(n);
for(int i = 0, a, b; i < n-1; ++i) {
cin >> a >> b;
--a, --b;
g[a].push_back(b);
g[b].push_back(a);
}

if(n & 1) {
cout << -1 << endl;
return 0;
}

DFS(0);
cout << res << endl;

return 0;
}
Copy The Code &

Input

cmd
4
2 4
4 1
3 1

Output

cmd
1