题目描述

给定一棵包含 $n$ 个顶点的树。选择一个顶点作为根顶点，满足以下条件。

• 对于所有的顶点 $v_1$ 和 $v_2$，如果 $distance(root, v_1) =distance(root, v_2)$，那么 $degree(v_1) =degree(v_2)$，其中$degree$ 表示与该顶点相连的顶点数，$distance$ 表示两个顶点之间的边数。

确定并找出是否存在这样的根顶点。如果有多个答案，找出其中任意一个。

输入格式

第一行包含一个整数 $n$ ，表示树的顶点数；

接下来的 $n-1$行，每行包含两个整数 $v_i$ 和 $u_i$（$1 \le v_i<u_i \le n$），表示存在一条边连接 $v_i$ 和 $u_i$。保证图形成一棵树。

输出格式

如果存在这样的根顶点，输出任意一个。否则，输出 −1。

7
1 2
2 3
3 4
4 5
3 6
6 7

3

6
1 3
2 3
3 4
4 5
4 6

-1

样例分析

这是第一个样例的图片。$1$、$5$、$7$也可以是有效答案。

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

数据范围与提示

对于 $100\%$ 的数据：$1 \le n \le 10^5$ 。