← 返回题目列表

Codeforces · 1182/D

D. 完整镜子

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

您给定的树由 $$$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$$$ 也可以是有效答案。

这是第二个示例的图片。可以看到,不可能找到这样的根顶点。