Tree Folding
Contest: Codeforces Round 397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)
Difficulty rating: 2200
Tags: dfs and similar, dp, greedy, implementation, trees

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 a0 = v, a1, ..., ak, and b0 = v, b1, ..., bk. Additionally, vertices a1, ..., ak, b1, ..., bk 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 b1, ..., bk 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.

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
6
1 2
2 3
2 4
4 5
1 6

Example output:
3

Example input:
7
1 2
1 3
3 4
1 5
5 6
6 7

Example output:
-1

Editorial:
Let's look at the performed actions in reverse. First, we have some path of odd length (by saying length we mean the number of edges} and double it several times. Now we do several "unfoldings". Among two leaves of this path exactly one (or its copy) participate in each unfolding; depending on it we call the unfolding "left" or "right". Note that left and right unfoldings have no edges in common; thus there is some vertex on the path which is not being unfolded. Let's call this vertex root.
Here is a criterion that a vertex can be a valid root. Root the tree at it and look at its certain subtree: the depths of all leaves there must be equal. Moreover, among all subtrees of the root there must be not more than 2 different depths of the leaves. This criterion follows directly if you look at the sequence of unfoldings.
Now we have a solution: for each directed edge in a tree compute a set of depths to the leaves by a 2-way tree DP (actually, it must be computed only if its size is at most 1). Afterwards for each vertex check the root criterion.
However, there is an idea which makes the solution simpler: the midpoint of the diameter of the given tree is always an appropriate root. Given this, we should only run a standard tree DP which checks if all leaves in a subtree have the same depth.
Here is the outline of a proof: in the path from the first paragraph select the leftmost and the rightmost possible root, now look through all possible distances from left root to the left leaf and from the right root to the right leaf. There are several configurations which are easy to check manually.