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
# LUOGU_RID: 106076897

import sys
from typing import Tuple
from Rerooting import Rerooting

input = lambda: sys.stdin.readline().rstrip("\r\n")
INF = int(4e18)

if __name__ == "__main__":
    n = int(input())
    edges = []
    for _ in range(n - 1):
        u, v = map(int, input().split())
        edges.append((u - 1, v - 1))

    E = Tuple[int, bool]

    def e(root: int) -> E:
        return (0, True)

    def op(childRes1: E, childRes2: E) -> E:
        dist1, _ = childRes1
        dist2, _ = childRes2
        return (max(dist1, dist2), dist1 == dist2)

    def composition(fromRes: E, parent: int, cur: int, direction: int) -> E:
        """direction: 0: cur -> parent, 1: parent -> cur"""
        dist, ok = fromRes
        return (dist + 1, ok)

    R = Rerooting(n)
    for u, v in edges:
        R.addEdge(u, v)

    dp = R.rerooting(e=e, op=op, composition=composition, root=0)
    res, ok = INF, False
    for i in range(n):
        dist, curOk = dp[i]
        if curOk:
            ok = True
            res = min(res, dist)
    if ok:
        print(res + 1)
    else:
        print(-1)

from typing import Callable, Generic, List, TypeVar

T = TypeVar("T")


class Rerooting(Generic[T]):

    __slots__ = ("adjList", "_n", "_decrement")

    def __init__(self, n: int, decrement: int = 0):
        self.adjList = [[] for _ in range(n)]
        self._n = n
        self._decrement = decrement

    def addEdge(self, u: int, v: int) -> None:
        u -= self._decrement
        v -= self._decrement
        self.adjList[u].append(v)
        self.adjList[v].append(u)

    def rerooting(
        self,
        e: Callable[[int], T],
        op: Callable[[T, T], T],
        composition: Callable[[T, int, int, int], T],
        root=0,
    ) -> List["T"]:
        root -= self._decrement
        assert 0 <= root < self._n
        parents = [-1] * self._n
        order = [root]
        stack = [root]
        while stack:
            cur = stack.pop()
            for next in self.adjList[cur]:
                if next == parents[cur]:
                    continue
                parents[next] = cur
                order.append(next)
                stack.append(next)

        dp1 = [e(i) for i in range(self._n)]
        dp2 = [e(i) for i in range(self._n)]
        for cur in order[::-1]:
            res = e(cur)
            for next in self.adjList[cur]:
                if parents[cur] == next:
                    continue
                dp2[next] = res
                res = op(res, composition(dp1[next], cur, next, 0))
            res = e(cur)
            for next in self.adjList[cur][::-1]:
                if parents[cur] == next:
                    continue
                dp2[next] = op(res, dp2[next])
                res = op(res, composition(dp1[next], cur, next, 0))
            dp1[cur] = res

        for newRoot in order[1:]:
            parent = parents[newRoot]
            dp2[newRoot] = composition(op(dp2[newRoot], dp2[parent]), parent, newRoot, 1)
            dp1[newRoot] = op(dp1[newRoot], dp2[newRoot])
        return dp1
