Vanya 想要最小化一棵树。他可以多次执行以下操作:选择一个顶点v,以及两条不相交(v除外)长度相等的路径a0 = v,a1,...,ak,b0 = v,b1,...,bk。此外,除了相应路径的相邻顶点之外,顶点 a1, ..., ak, b1, ..., bk 在树中不得有任何邻居。之后,其中一条路径可能会合并到另一条路径中,即可以有效擦除顶点 b1, ..., bk:
帮助 Vanya 确定是否可以通过一系列描述的操作将树变成路径,如果答案是肯定的,还确定该路径的最短长度。
输入
输入的第一行包含顶点数 n (2 ≤ n ≤ 2·105)。
接下来的 n - 1 行描述树的边。每条线都包含两个空格分隔的整数 u 和 v (1 ≤ u, v ≤ n, u ≠ v) - 相应边端点的索引。保证给定的图是一棵树。
输出
如果无法获取路径,则打印-1。否则,打印可能路径中的最小边数。
示例
输入 #1
6 1 2 2 3 2 4 4 5 1 6
输出 #1
3
输入 #2
7 1 2 1 3 3 4 1 5 5 6 6 7
输出 #2
-1
注意
在第一个示例案例中,合并路径 2 - 1 - 6 和 2 - 4 - 5 后获得三个边缘的路径。
无法在第二个示例案例中执行任何操作。例如,不可能合并路径1-3-4和1-5-6,因为顶点6另外具有不存在于相应路径中的邻居7。