您给定的树由 $$$n$$$ 个顶点组成。选择满足以下条件的顶点作为根顶点。
- 对于所有顶点 $$$v_{1}$$$ 和 $$$v_{2}$$$,如果 $$$distance$$$($$$root$$$, $$$v_{1}$$$) $$$= distance$$$($$$root$$$, $$$v_{2})$$$ 则$$$ Degree$$$($$$v_{1}$$$)$$$= Degree$$$($$$v_{2}$$$),其中$$$ Degree$$$表示连接到该顶点的顶点数,$$$distance$$$表示两个顶点之间的边数。
判断树中是否存在这样的根顶点。如果有多个答案,请找出其中一个。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — 顶点数。
接下来的 $$$n-1$$$ 行包含两个整数 $$$v_{i}$$$ 和 $$$u_{i}$$$ ($$$1 \le v_{i} \lt u_{i} \le n$$$) - 这意味着 $$$v_{i}$$$ 和 $$$u_{i}$$$ 之间存在一条边。保证图形成树。
输出
如果存在这样的根顶点,则打印其中的任何一个。否则,打印$$$-1$$$。
示例
输入 #1
7 1 2 2 3 3 4 4 5 3 6 6 7
输出 #1
3
输入 #2
6 1 3 2 3 3 4 4 5 4 6
输出 #2
-1
注意
这是第一个示例的图片。 $$$1$$$、$$$5$$$、$$$7$$$ 也可以是有效答案。
这是第二个示例的图片。可以看到,不可能找到这样的根顶点。