← 返回题目列表

Codeforces · 765/E

E. 树折叠

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

Vanya 想要最小化一棵树。他可以多次执行以下操作:选择一个顶点v,以及两条不相交(v除外)长度相等的路径a0 = v,a1,...,ak,b0 = v,b1,...,bk。此外,除了相应路径的相邻顶点之外,顶点 a1, ..., ak, b1, ..., bk 在树中不得有任何邻居。之后,其中一条路径可能会合并到另一条路径中,即可以有效擦除顶点 b1, ..., bk:

帮助 Vanya 确定是否可以通过一系列描述的操作将树变成路径,如果答案是肯定的,还确定该路径的最短长度。

输入

输入的第一行包含顶点数 n (2 ≤ n ≤ 2·105)。

接下来的 n - 1 行描述树的边。每条线都包含两个空格分隔的整数 u 和 v (1 ≤ u, v ≤ n, u ≠ v) - 相应边端点的索引。保证给定的图是一棵树。

输出

如果无法获取路径,则打印-1。否则,打印可能路径中的最小边数。

示例

输入 #1

6
1 2
2 3
2 4
4 5
1 6

输出 #1

3

输入 #2

7
1 2
1 3
3 4
1 5
5 6
6 7

输出 #2

-1

注意

在第一个示例案例中,合并路径 2 - 1 - 6 和 2 - 4 - 5 后获得三个边缘的路径。

无法在第二个示例案例中执行任何操作。例如,不可能合并路径1-3-4和1-5-6,因为顶点6另外具有不存在于相应路径中的邻居7。