CF982C Cut 'em all!

题目描述

现在有一棵有 $n$ 个节点的树,你可以删去树中的一些边使其成为森林,你的任务是删去最多的边使得每一棵森林中的树的大小为偶数,并输出删去的边数。

输入格式

第一行为一个整数,即节点数 $n(1 \le n \le 10^5)$ 接下来 $n-1$ 行每行包括两个整数 $u$ 和 $v$,表示树中连接 $u$ 和 $v$ 的两条边。保证 $u$ 和 $v$ 在 $1$ 至 $n$ 的范围内,同时保证给出的图是一棵树。

输出格式

一个整数,表示你可以删去的最多的边数。如果没有可行方案,输出 `-1`。

说明/提示

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