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
class Answer(Exception):
	def __init__(self, answer):
		super(Answer, self).__init__()
		self.answer = answer


class Node:
	UNDEF = -1

	def __init__(self, name=None):
		self.name = name
		self.neighbour_nodes = []
		self.height = None
		self.edge_heights = None
		pass

	def sym_add_node(self, node):
		self.neighbour_nodes.append(node)
		node.neighbour_nodes.append(self)

	def calc_height_dfs(self, fr):
		heights = set()
		for node in self.neighbour_nodes:
			if node != fr:
				node.calc_height_dfs(self)
				heights.add(node.height)

		if len(heights) == 0:
			#list
			self.height = 0
		elif len(heights) == 1 and Node.UNDEF not in heights:
			self.height = list(heights)[0] + 1
		else:
			self.height = Node.UNDEF

	def optimize_dfs(self, fr):
		if len(self.neighbour_nodes) <= 3:
			return 

		heights = {}
		for i in range(len(self.neighbour_nodes)-1, -1, -1):
			node = self.neighbour_nodes[i]
			if node != fr:
				h = node.height
				
				if h in heights and h != Node.UNDEF:
					self.neighbour_nodes.pop(i)
					# optimize node

				else:
					if h not in heights:
						heights[h] = []
			
					heights[h].append(node)

		if len(self.neighbour_nodes) > 3:
			raise Answer(-1)


	def dfs_call(self, func, fr):
		for node in self.neighbour_nodes:
			if node != fr:
				node.dfs_call(func, self)
		func(self)

	def get_height_by_edges(self, fr):
		heights = []
		for node, h in zip(self.neighbour_nodes, self.edge_heights):
			if node != fr:
				heights.append(h)
		heights = set(heights)
		if len(heights) == 0:
			return 1
		elif len(heights) == 1 and Node.UNDEF not in heights:
			return list(heights)[0] + 1
		else:
			return Node.UNDEF

	def calc_edge_heights_dfs(self, fr):
		if self.edge_heights is None:
			self.edge_heights = [None] * len(self.neighbour_nodes)

		for i in range(len(self.neighbour_nodes)):
			node = self.neighbour_nodes[i]
			if node != fr:
				if self.edge_heights[i] is None:
					node.calc_edge_heights_dfs(self)
					self.edge_heights[i] = node.get_height_by_edges(self)

	def calc_answer(self):
		all_edge_heights = set(self.edge_heights)
		if len(all_edge_heights) <= 2 \
			and Node.UNDEF not in all_edge_heights:
			
			answer = sum(all_edge_heights)
			while answer % 2 == 0:
				answer //= 2
			raise Answer(answer)


def main():
	n = int(input())
	nodes = [Node(i) for i in range(n)]

	for i in range(n-1):
		a, b = map(int, input().strip().split())
		nodes[a-1].sym_add_node(nodes[b-1])

	try:
		#optimize
		nodes[0].calc_height_dfs(None)
		nodes[0].optimize_dfs(None)


		#calc_answer
		nodes[0].dfs_call(lambda node: node.calc_edge_heights_dfs(None), None)
		nodes[0].dfs_call(lambda node: node.calc_answer(), None)

	except Answer as a:
		print(a.answer)
	else:
		print(-1)


main()