给你一棵有 $$$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$$$。