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 a0 = v, a1, ..., ak, and b0 = v, b1, ..., bk. Additionally, vertices a1, ..., ak, b1, ..., bk 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 b1, ..., bk can be effectively erased:

<image>

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.

Input

The first line of input contains the number of vertices n (2 ≤ n ≤ 2·105).

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.

Output

If it is impossible to obtain a path, print -1. Otherwise, print the minimum number of edges in a possible path.

Examples

Input

6
1 2
2 3
2 4
4 5
1 6


Output

3


Input

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


Output

-1

Note

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.
//package e_contest_9;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class treeFolding2 {
	static int[][] adjList;
	static int n;
	static int [] levels;
	static class pair{
		int one, two;
		public pair(int one, int two) {
			this.one = one;
			this.two = two;
		}
	}
	public static void main(String[] args) throws IOException{
		Scanner sc= new Scanner(System.in);
		n =sc.nextInt();
		int [] count = new int[n];
		adjList =new  int[n][];
		pair [] data = new pair[n-1];
		for (int i = 0; i < n-1; i++) {
			int one =sc.nextInt()-1, two =sc.nextInt()-1;
			count[one]++;
			count[two]++;
			data[i] =new pair(one, two);
		}
		for (int i = 0; i < adjList.length; i++) {
			adjList[i] =new int[count[i]];
		}
		Arrays.fill(count,0);
		for (int i = 0; i < n-1; i++) {
			int one =data[i].one, two =data[i].two;
			adjList[one][count[one]++]=two;
			adjList[two][count[two]++]=one;
		}
		levels =new int[n];
		Arrays.fill(levels, -1);
		levels[0] = 0;
		Queue<Integer> q =new LinkedList<Integer>();
		q.add(0);
		int idx = 0;
		int deepestLevel =0;
		while(!q.isEmpty()) {
			int top = q.remove();
			int curLevel = levels[top];
			if(curLevel>deepestLevel) {
				deepestLevel = curLevel;
				idx = top;
			}
			for (int i = 0; i < adjList[top].length; i++) {
				int nxt = adjList[top][i];
				if(levels[nxt]==-1)
				{
					levels[nxt] =curLevel+1;
					q.add(nxt);
				}
				
			}
		}
		int [] parents = new int[n];
		Arrays.fill(levels, -1);
		q.add(idx);
		parents[idx]=-1;
		levels[idx]=0;
		int max = -1;
		int child = 0;
		deepestLevel =0;
		while(!q.isEmpty()) {
			
			int top = q.remove();
			int curLevel = levels[top];
			if(max<curLevel) {
				max = curLevel;
				child = top;
			}
			if(curLevel>deepestLevel) {
				deepestLevel = curLevel;
			}
			for (int i = 0; i < adjList[top].length; i++) {
				int nxt = adjList[top][i];
				if(levels[nxt]==-1)
				{
					parents[nxt] = top;
					levels[nxt] =curLevel+1;
					q.add(nxt);
				}
				
			}
		}
//		System.out.println(deepestLevel);
		deepestLevel+=1;
		ArrayList<Integer> path = new ArrayList<Integer>();
		path.add(child);
		int parent = parents[child];
		while(parent!=-1) {
			path.add(parent);
			parent = parents[parent];
		}
//		System.out.println(path.toString());
		if(deepestLevel%2==0) {
			if(deepestLevel==2) {
				System.out.println(1);
			}else {
			int countRight = deepestLevel/2-1;
			vis = new boolean[n];
			int idxRight =path.get(countRight);
			vis = new boolean[n];
			int countLeft = deepestLevel/2;
			int idxLeft = path.get(countLeft);
//			System.out.println(countRight+" "+countLeft);
//			System.out.println(idxRight+" "+idxLeft);
//			System.out.println(idxRight+" "+idxLeft);
			leaves =new ArrayList<Integer>();
			vis =new boolean[n];
			dfs2(idxRight, idxLeft);
			
			
			Arrays.fill(levels, -1);
			q.add(idxRight);
			levels[idxRight]=0;
			while(!q.isEmpty()) {
				int top = q.remove();
				int curLevel = levels[top];
				for (int i = 0; i < adjList[top].length; i++) {
					int nxt = adjList[top][i];
					if(levels[nxt]==-1)
					{
						levels[nxt] =curLevel+1;
						q.add(nxt);
					}
					
				}
			}
			
			
			
			int lenPrev = levels[leaves.get(0)];
			boolean good = true;
			for (int i = 1; i < leaves.size(); i++) {
				int lenCur = levels[leaves.get(i)];
				if(lenCur!=lenPrev)
					good = false;
			}
			if(good) {
				leaves =new ArrayList<Integer>();
				vis =new boolean[n];
				dfs2(idxLeft, idxRight);
				Arrays.fill(levels, -1);
				q.add(idxLeft);
				levels[idxLeft]=0;
				while(!q.isEmpty()) {
					int top = q.remove();
					int curLevel = levels[top];
					for (int i = 0; i < adjList[top].length; i++) {
						int nxt = adjList[top][i];
						if(levels[nxt]==-1)
						{
							levels[nxt] =curLevel+1;
							q.add(nxt);
						}
						
					}
				}
				lenPrev = levels[leaves.get(0)];
				good = true;
				for (int i = 1; i < leaves.size(); i++) {
					int lenCur = levels[leaves.get(i)];
					if(lenCur!=lenPrev)
						good = false;
				}
			}
			if(good) {
				while(deepestLevel%2==1&&deepestLevel!=1)
					deepestLevel-=deepestLevel/2;
				System.out.println(deepestLevel-1);
			}else
				System.out.println(-1);
			}
		}else {
			int countRight = (deepestLevel/2);
			vis =new boolean[n];
			int idxRight =path.get(countRight);
			HashSet<Integer> hs =new HashSet<Integer>();
			boolean good = true;
			int [] directChildren = adjList[idxRight];
			int first = -1;
			int two = -1;
			Arrays.fill(levels, -1);
			for(int j = 0;j<directChildren.length&&good;j++) {
				int curChild = directChildren[j];
				levels[curChild]=0;
				q.add(curChild);
				int len = -1;
				while(!q.isEmpty()) {
					int top = q.remove();
//					System.out.println(top==7);
					int curLevel = levels[top];
					boolean nonLeaf = false;
					for (int i = 0; i < adjList[top].length; i++) {
						int nxt = adjList[top][i];
						if(nxt==idxRight)
							continue;
						if(levels[nxt]==-1)
						{
//							System.out.println("Hi"+" "+nxt+" "+curChild);
							nonLeaf= true;
							levels[nxt] =curLevel+1;
							q.add(nxt);
						}
						
					}
					if(!nonLeaf) {
//						System.out.println(curChild+" "+curLevel);
						if(len==-1)
							len = curLevel;
						else
							if(len!=curLevel) {
								good = false;
//								System.out.println(curChild+" "+top+ " "+curLevel);
//								System.out.println("hello");
							}
					}
				}
				if(first==-1)
					first = len+1;
				else
					if(first!=(len+1))
						two = len+1;
				hs.add(len+1);
			}
//			System.out.println(first+" hello  "+two);
			if(hs.size()==1&& good) {
				first+=1;
				while(first%2==1&&first!=1)
					first-=first/2;
				System.out.println(first-1);
			}else if(hs.size()==2&& good) {
				first+=two+1;
				while(first%2==1&&first!=1)
					first-=first/2;
				System.out.println(first-1);
			}else {
				System.out.println(-1);
			}
			
		}
	}
	static ArrayList<Integer> leaves;
	static boolean [] vis;
	static void dfs2(int idx, int leave) {
		int valid = 0;
		vis[idx] =true;
		for (int i = 0; i < adjList[idx].length; i++) {
			int nxt = adjList[idx][i];
			if(vis[nxt]||nxt ==leave)
				continue;
			dfs2(nxt, leave);
			valid++;
		}
		if(valid==0)
			leaves.add(idx);
	}//
	static int dfs(int idx, int counter ) {
		if(counter==0)
			return idx;
		vis[idx] = true;
		for (int i = 0; i < adjList[idx].length; i++) {
			int nxt = adjList[idx][i];
			if(vis[nxt])
				continue;
			int poss = dfs(nxt, counter-1);
			if(poss!=-1)
				return poss;
		}
		return -1;
	}
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
		
		public double nextDouble() throws IOException
		{
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if(x.charAt(0) == '-')
			{
				neg = true;
				start++;
			}
			for(int i = start; i < x.length(); i++)
				if(x.charAt(i) == '.')
				{
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				}
				else
				{
					sb.append(x.charAt(i));
					if(dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg?-1:1);
		}
		
		public boolean ready() throws IOException {return br.ready();}


	}



}
