Complete Mirror
Contest: Codeforces Round 566 (Div. 2)
Difficulty rating: 2400
Tags: constructive algorithms, dfs and similar, dp, hashing, implementation, trees

You have given tree consist of $$$n$$$ vertices. Select a vertex as root vertex that satisfies the condition below.

- For all vertices $$$v_{1}$$$ and $$$v_{2}$$$, if $$$distance$$$($$$root$$$, $$$v_{1}$$$) $$$= distance$$$($$$root$$$, $$$v_{2})$$$ then $$$degree$$$($$$v_{1}$$$) $$$= degree$$$($$$v_{2}$$$), where $$$degree$$$ means the number of vertices connected to that vertex, and $$$distance$$$ means the number of edges between two vertices.

Determine and find if there is such root vertex in the tree. If there are multiple answers, find any of them.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — the number of vertices.

Each of the next $$$n-1$$$ lines contains two integers $$$v_{i}$$$ and $$$u_{i}$$$ ($$$1 \le v_{i} \lt u_{i} \le n$$$) — it means there is an edge exist between $$$v_{i}$$$ and $$$u_{i}$$$. It is guaranteed that the graph forms tree.

Output format:
If there is such root vertex exists, print any of them. Otherwise, print $$$-1$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
This is the picture for the first example. $$$1$$$, $$$5$$$, $$$7$$$ also can be a valid answer.

This is the picture for the second example. You can see that it's impossible to find such root vertex.

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

Example output:
3

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

Example output:
-1

Editorial:
First, the valid tree should form like the picture below unless the whole tree is completely linear.
• top: This node is the top of the tree. This node has always degree $$$1$$$. This node is always one of the possible answers of valid tree. There might be no top node in the tree.
• semitop: This node is the closest children from the top node that satisfies $$$degree >= 3$$$. In other words, this node is the end of the leaf branch which includes top node as leaf. This node can be one of the possible answers of valid tree. If there is no semitop in the tree, the whole tree is invalid.
• mid level: This is the area of nodes between semitop node and semibottom nodes.
• semibottom: These nodes are the closest ancestors from each leaf nodes which satisfies $$$degree >= 3$$$. In other words, these nodes are the end of each leaf branches.
• bottom: These nodes are the leaves except top node.
And also let's define $$$u_{1}$$$ and $$$u_{2}$$$ are directly reachable if there are only nodes with $$$degree = 2$$$ between $$$u_{1}$$$ and $$$u_{2}$$$ exclusive.
There are two ways to find the top node and the semitop node.
1. Lawali's solution. Find the diameter path and validate for two leaves of the diameter path. If no valid vertex found(i.e. top is not in the diameter path), then the semitop should be the middle of the diameter path. Now validate for the semitop and the closest directly reachable leaf from semitop. If any valid vertex found, print it. Otherwise print $$$-1$$$.  The first case of diameter path in valid tree. Semitop node is the middle of diameter path. The second case of diameter path in valid tree. Top node is the end of diameter path.
2. McDic's solution. Clone the whole tree and cut the leaf branches(include top) from the cloned tree. Let's call this tree as "inner tree". Inner tree consists of only semitop, mid level nodes and semibottom nodes. Then you can find the semitop by collapsing each level from leaf nodes of inner tree. Now validate for semitop, the furthest directly reachable leaf node from semitop, and the closest directly reachable leaf node from semitop. It is guaranteed that the top node is one of those two leaves. If any valid vertex found, print it. Otherwise print $$$-1$$$.  This is the inner tree of original tree. You can find the semitop easier than before since top is removed in inner tree.
Time complexity is $$$O(n)$$$.