Cut 'em all!

题意翻译

题目描述 现在有一棵有N个节点的树，你可以删去树中的一些边使其成为森林，你的任务是删去最多的边使得每一棵森林中的树的大小为偶数，并输出删去的边数。 输入格式 第一行为一个整数，即节点数N（1<=n<=1e5） 接下来N-1行每行包括两个整数u和v，表示树中连接u和v的两条边。保证u和v在1至N的范围内，同时保证给出的图是一棵树。 输出格式 一个整数，表示你可以删去的最多的边数。

题目描述

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.

输入输出样例

输入样例 #1

4
2 4
4 1
3 1

输出样例 #1

1

输入样例 #2

3
1 2
1 3

输出样例 #2

-1

输入样例 #3

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

输出样例 #3

4

输入样例 #4

2
1 2

输出样例 #4

0

说明

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