CF765E.Tree Folding

Vanya wants to minimize a tree. He can perform the following operation multiple times: choose a vertex v, and two disjoint (except for v) paths of equal length _a_0 = v, _a_1, ..., a__k, and _b_0 = v, _b_1, ..., b__k. Additionally, vertices _a_1, ..., a__k, _b_1, ..., b__k must not have any neighbours in the tree other than adjacent vertices of corresponding paths. After that, one of the paths may be merged into the other, that is, the vertices _b_1, ..., b__k can be effectively erased:

Help Vanya determine if it possible to make the tree into a path via a sequence of described operations, and if the answer is positive, also determine the shortest length of such path.

万尼亚希望将一棵树最小化。他可以多次执行以下操作：选择一个顶点 $v$，以及两条长度相等且仅在 $v$ 处相交（即不相交于其他顶点）的路径：$a_0 = v, a_1, \dots, a_k$ 和 $b_0 = v, b_1, \dots, b_k$；此外，顶点 $a_1, \dots, a_k, b_1, \dots, b_k$ 在树中除对应路径上的相邻顶点外，不能有其他邻接点。随后，可将其中一条路径合并到另一条上，即顶点 $b_1, \dots, b_k$ 可被有效删除：

请帮助万尼亚判断：能否通过若干次上述操作将该树变为一条路径？若可以，请进一步求出所得路径的最短长度。

The first line of input contains the number of vertices n (2 ≤ n ≤ 2·105).

Next n - 1 lines describe edges of the tree. Each of these lines contains two space-separated integers u and v (1 ≤ u, v ≤ n, u ≠ v) — indices of endpoints of the corresponding edge. It is guaranteed that the given graph is a tree.

输入的第一行包含顶点数 $n$（$2 \leq n \leq 2\cdot10^5$）。

接下来的 $n - 1$ 行描述树的边。每行包含两个以空格分隔的整数 $u$ 和 $v$（$1 \leq u, v \leq n$，且 $u \neq v$），表示对应边的两个端点的下标。保证所给图是一棵树。

If it is impossible to obtain a path, print -1. Otherwise, print the minimum number of edges in a possible path.

如果无法获得路径，则输出 -1。否则，输出可能路径中边的最小数量。

In the first sample case, a path of three edges is obtained after merging paths 2 - 1 - 6 and 2 - 4 - 5.

It is impossible to perform any operation in the second sample case. For example, it is impossible to merge paths 1 - 3 - 4 and 1 - 5 - 6, since vertex 6 additionally has a neighbour 7 that is not present in the corresponding path.

在第一个样例中，合并路径 $2\text{-}1\text{-}6$ 和 $2\text{-}4\text{-}5$ 后得到一条包含三条边的路径。

在第二个样例中，无法执行任何操作。例如，无法合并路径 $1\text{-}3\text{-}4$ 和 $1\text{-}5\text{-}6$，因为顶点 $6$ 还有一个邻居 $7$，而该邻居未出现在对应的路径中。