Vanya wants to minimize a tree. He can perform the following operation multiple times: choose a vertex *v*, and two disjoint (except for *v*) paths of equal length *a*<sub class="lower-index">0</sub> = *v*, *a*<sub class="lower-index">1</sub>, ..., *a*<sub class="lower-index">*k*</sub>, and *b*<sub class="lower-index">0</sub> = *v*, *b*<sub class="lower-index">1</sub>, ..., *b*<sub class="lower-index">*k*</sub>. Additionally, vertices *a*<sub class="lower-index">1</sub>, ..., *a*<sub class="lower-index">*k*</sub>, *b*<sub class="lower-index">1</sub>, ..., *b*<sub class="lower-index">*k*</sub> must not have any neighbours in the tree other than adjacent vertices of corresponding paths. After that, one of the paths may be merged into the other, that is, the vertices *b*<sub class="lower-index">1</sub>, ..., *b*<sub class="lower-index">*k*</sub> can be effectively erased:

Help Vanya determine if it possible to make the tree into a path via a sequence of described operations, and if the answer is positive, also determine the shortest length of such path.
The first line of input contains the number of vertices *n* (2 ≤ *n* ≤ 2·10<sup class="upper-index">5</sup>).

Next *n* - 1 lines describe edges of the tree. Each of these lines contains two space-separated integers *u* and *v* (1 ≤ *u*, *v* ≤ *n*, *u* ≠ *v*) — indices of endpoints of the corresponding edge. It is guaranteed that the given graph is a tree.
In the first sample case, a path of three edges is obtained after merging paths 2 - 1 - 6 and 2 - 4 - 5.

It is impossible to perform any operation in the second sample case. For example, it is impossible to merge paths 1 - 3 - 4 and 1 - 5 - 6, since vertex 6 additionally has a neighbour 7 that is not present in the corresponding path.
6
1 2
2 3
2 4
4 5
1 6
3
7
1 2
1 3
3 4
1 5
5 6
6 7
-1
2
1 2
1
3
3 1
1 2
1
10
5 10
7 8
8 3
2 6
3 2
9 7
4 5
10 1
6 4
9
11
11 9
6 7
7 1
8 11
5 6
3 5
9 3
10 8
2 4
4 10
5
10
4 2
7 4
2 6
2 5
4 8
10 3
2 9
9 1
5 10
-1
11
8 9
2 7
1 11
3 2
9 1
8 5
8 6
5 4
4 10
8 3
1
12
12 6
6 7
8 11
4 8
10 4
12 3
2 10
6 2
12 9
4 1
9 5
-1
4
4 1
4 3
4 2
1
5
1 5
2 3
2 4
1 2
3
6
1 6
3 1
6 4
5 3
2 5
5
7
5 6
5 7
5 1
7 4
6 3
3 2
-1
8
6 1
4 7
4 8
8 5
7 6
4 3
4 2
-1
3
1 3
3 2
1
5
5 4
4 3
3 1
5 2
1
9
1 2
1 3
1 4
1 5
1 6
6 7
6 8
8 9
3
import sys
input = lambda : sys.stdin.readline().rstrip()


write = lambda x: sys.stdout.write(x+"\n")
debug = lambda x: sys.stderr.write(x+"\n")
writef = lambda x: print("{:.12f}".format(x))


"""全方位木DPrerooting
"""
n = int(input())
ns = [[] for _ in range(n)]
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append(v)
    ns[v].append(u)

# リストなどを使う場合、ラムダ式にする
unit = 0 # (部分木サイズ, 通り数) など
def merge(val, other):
    """注意: unitについて不変になるように定義する
    val と otherの演算順序 (一方がunitなら他方を返す、みたいにする)
    """
    if val==other:
        return val
    elif val==0:
        return other
    return -1
def add_node(val,u): # 木DPで戻るときに1頂点(u)を加える処理
    if val==-1:
        return -1
    return val+1

root = 0
s = [root]
d0 = [-1]*n # d0[u]: u以下の部分木に関する情報
d1 = [-1]*n # d1[u]: parent[u]以上の部分木に関する情報
parent = [-1]*n
parent[root] = root
order = [] # 行きがけ順を記録
while s:
    u = s.pop()
    if u<0:
        # 返るときの処理
        u = ~u
        val = unit
        for v in ns[u]:
            if parent[v]!=u:
                continue
            val = merge(val, d0[v])
        # 部分木の根を追加する処理
        d0[u] = add_node(val,u)
    else:
        order.append(u)
        s.append(~u)
        for v in ns[u]:
            # 進むときの処理
            if parent[v]>=0:
                continue
            s.append(v)
            parent[v] = u
d1[root] = unit
inf = 10**12
ans = inf
for u in order:
    cl = [unit] # 左からの累積和
    cr = [unit] # 右からの累積和
    vl = unit
    vr = unit
    l = len(ns[u])
    for i in range(l):
        v = ns[u][i]
        if parent[v]==u:
            vl = merge(vl, d0[v])
            cl.append(vl)
        v = ns[u][l-1-i]
        if parent[v]==u:
            vr = merge(vr, d0[v])
            cr.append(vr)
    cr = cr[::-1]
    i = 0
    for v in ns[u]:
        if parent[v]!=u:
            continue
        val = merge(merge(d1[u], cl[i]), cr[i+1])
        d1[v] = add_node(val,u)
        i += 1
    # uの答えを計算
    if d1[u]>=0:
        count = {}
        count[d1[u]] = 1
        for v in ns[u]:
            if v==parent[u]:
                continue
            c = d0[v]
            if c==-1:
                break
            count.setdefault(c,0)
            count[c] += 1
            if len(count)>2:
                break
        else:
            kvs = list(count.items())
            if len(kvs)==1:
                ans = min(ans, kvs[0][0])
            else:
                ans = min(ans, kvs[0][0]+kvs[1][0])
if ans==inf:
    ans = -1
print(ans)