QYcode QYcode

CF982C.Cut 'em all!

传统题 时间 2000 ms 内存 256 MiB 8 尝试 22 已通过 8 标签

Cut 'em all!

English 简体中文

题目描述

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

输入格式

第一行为一个整数，即节点数 n(1≤n≤105)n(1 \le n \le 10^5)

接下来 n−1n-1 行每行包括两个整数 uu 和 vv，表示树中连接 uu 和 vv 的两条边。保证 uu 和 vv 在 11 至 nn 的范围内，同时保证给出的图是一棵树。

输出格式

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

样例

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

在线编程 IDE

建议全屏模式获得最佳体验

操作

  1. 登录后递交
  3. 讨论 (0)
  4. 题解 (0)
  5. 提交统计