← 返回题目列表

Codeforces · 982/C

C. 全部砍掉!

中文机器翻译题面 查看原题

给你一棵有 $$$n$$$ 个顶点的树。

您的任务是确定可以删除的最大边数,以使所有剩余的连接组件具有均匀的大小。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) 表示树的大小。

接下来的 $$$n - 1$$$ 行分别包含两个整数 $$$u$$$、$$$v$$$ ($$$1 \le u, v \le n$$$),描述由第 $$$i$$$ 条边连接的顶点。

保证给定的边形成一棵树。

输出

输出单个整数 $$$k$$$ — 可以删除以使所有连接的组件具有均匀大小的边的最大数量,如果无法删除边以满足此属性,则输出 $$$-1$$$。

示例

输入 #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

注意

在第一个示例中,您可以删除顶点 $$$1$$$ 和 $$$4$$$ 之间的边。之后的图将有两个连接的组件,每个组件有两个顶点。

在第二个示例中,您无法以所有组件都具有偶数个顶点的方式删除边,因此答案是 $$$-1$$$。