You have unweighted tree of n vertices. You have to assign a positive weight to each edge so that the following condition would hold:

  * For every two different leaves v_{1} and v_{2} of this tree, [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of weights of all edges on the simple path between v_{1} and v_{2} has to be equal to 0. 



Note that you can put very large positive integers (like 10^{(10^{10})}).

It's guaranteed that such assignment always exists under given constraints. Now let's define f as the number of distinct weights in assignment.

<image> In this example, assignment is valid, because bitwise XOR of all edge weights between every pair of leaves is 0. f value is 2 here, because there are 2 distinct edge weights(4 and 5).

<image> In this example, assignment is invalid, because bitwise XOR of all edge weights between vertex 1 and vertex 6 (3, 4, 5, 4) is not 0. 

What are the minimum and the maximum possible values of f for the given tree? Find and print both.

Input

The first line contains integer n (3 ≤ n ≤ 10^{5}) — the number of vertices in given tree.

The i-th of the next n-1 lines contains two integers a_{i} and b_{i} (1 ≤ a_{i} < b_{i} ≤ n) — it means there is an edge between a_{i} and b_{i}. It is guaranteed that given graph forms tree of n vertices.

Output

Print two integers — the minimum and maximum possible value of f can be made from valid assignment of given tree. Note that it's always possible to make an assignment under given constraints.

Examples

Input


6
1 3
2 3
3 4
4 5
5 6


Output


1 4


Input


6
1 3
2 3
3 4
4 5
4 6


Output


3 3


Input


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


Output


1 6

Note

In the first example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum. 

<image>

In the second example, possible assignments for each minimum and maximum are described in picture below. The f value of valid assignment of this tree is always 3. 

<image>

In the third example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum. 

<image>
	import java.io.*;
	import java.util.*;
	
	public class B implements Runnable {
		boolean judge = false;
		FastReader scn;
		PrintWriter out;
		String INPUT = "";
	
		void solve() {
			int n = scn.nextInt();
			int[] from = new int[n - 1], to = new int[n - 1];
			for (int i = 0; i < n - 1; i++) {
				from[i] = scn.nextInt() - 1;
				to[i] = scn.nextInt() - 1;
			}
			int[][] g = packU(n, from, to);
			
			if(n == 3) {
				out.println("1 1");
				return;
			}
	
			if (isLadder(g)) {
				out.println((n % 2 == 1 ? 1 : 3) + " " + (n - 1));
				return;
			}
	
			int[] depth = new int[n];
			dfs(g, depth, 0, -1, 0);
			
			boolean[] leaf = new boolean[n];
			
			int minA = -1;
			for(int i = 0; i < n; i++) {
				if(g[i].length == 1) {
					leaf[i] = true;
					if(minA == -1 || minA == depth[i] % 2) {
						minA = depth[i] % 2;
					} else {
						minA = 3;
					}
				}
			}
			
			if(minA != 3) {
				minA = 1;
			}
			
			int max = n - 1;
			for(int i = 0; i < n; i++) {
				int x = 0;
				for(int v : g[i]) {
					if(leaf[v]) {
						x++;
					}
				}
				if(x > 1) {
					max -= (x - 1);
				}
			}
			
			out.println(minA + " " + max);
		}
	
		void dfs(int[][] g, int[] depth, int u, int p, int d) {
			depth[u] = d;
			for(int v : g[u]) {
				if(v != p) {
					dfs(g, depth, v, u, d + 1);
				}
			}
		}
	
		boolean isLadder(int[][] g) {
			int max = 0;
			for (int i = 0; i < g.length; i++) {
				max = Math.max(max, g[i].length);
			}
			return max <= 2;
		}
	
		int[][] packU(int n, int[] from, int[] to) {
			int[][] g = new int[n][];
			int[] p = new int[n];
			for (int f : from)
				p[f]++;
			for (int t : to)
				p[t]++;
			for (int i = 0; i < n; i++)
				g[i] = new int[p[i]];
			for (int i = 0; i < from.length; i++) {
				g[from[i]][--p[from[i]]] = to[i];
				g[to[i]][--p[to[i]]] = from[i];
			}
			return g;
		}
	
		public void run() {
			long time = System.currentTimeMillis();
			boolean oj = System.getProperty("ONLINE_JUDGE") != null || judge;
			out = new PrintWriter(System.out);
			scn = new FastReader(oj);
			solve();
			out.flush();
			if (!oj) {
				System.out.println(Arrays.deepToString(new Object[] { System.currentTimeMillis() - time + " ms" }));
			}
		}
	
		public static void main(String[] args) {
			new Thread(null, new B(), "Main", 1 << 28).start();
		}
	
		class FastReader {
			InputStream is;
	
			public FastReader(boolean onlineJudge) {
				is = onlineJudge ? System.in : new ByteArrayInputStream(INPUT.getBytes());
			}
	
			byte[] inbuf = new byte[1024];
			public int lenbuf = 0, ptrbuf = 0;
	
			int readByte() {
				if (lenbuf == -1)
					throw new InputMismatchException();
				if (ptrbuf >= lenbuf) {
					ptrbuf = 0;
					try {
						lenbuf = is.read(inbuf);
					} catch (IOException e) {
						throw new InputMismatchException();
					}
					if (lenbuf <= 0)
						return -1;
				}
				return inbuf[ptrbuf++];
			}
	
			boolean isSpaceChar(int c) {
				return !(c >= 33 && c <= 126);
			}
	
			int skip() {
				int b;
				while ((b = readByte()) != -1 && isSpaceChar(b))
					;
				return b;
			}
	
			double nextDouble() {
				return Double.parseDouble(next());
			}
	
			char nextChar() {
				return (char) skip();
			}
	
			String next() {
				int b = skip();
				StringBuilder sb = new StringBuilder();
				while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
					sb.appendCodePoint(b);
					b = readByte();
				}
				return sb.toString();
			}
	
			String nextLine() {
				int b = skip();
				StringBuilder sb = new StringBuilder();
				while ((!isSpaceChar(b) || b == ' ')) { // when nextLine, (isSpaceChar(b) && b != ' ')
					sb.appendCodePoint(b);
					b = readByte();
				}
				return sb.toString();
			}
	
			char[] next(int n) {
				char[] buf = new char[n];
				int b = skip(), p = 0;
				while (p < n && !(isSpaceChar(b))) {
					buf[p++] = (char) b;
					b = readByte();
				}
				return n == p ? buf : Arrays.copyOf(buf, p);
			}
	
			int nextInt() {
				int num = 0, b;
				boolean minus = false;
				while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
					;
				if (b == '-') {
					minus = true;
					b = readByte();
				}
	
				while (true) {
					if (b >= '0' && b <= '9') {
						num = num * 10 + (b - '0');
					} else {
						return minus ? -num : num;
					}
					b = readByte();
				}
			}
	
			long nextLong() {
				long num = 0;
				int b;
				boolean minus = false;
				while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
					;
				if (b == '-') {
					minus = true;
					b = readByte();
				}
	
				while (true) {
					if (b >= '0' && b <= '9') {
						num = num * 10 + (b - '0');
					} else {
						return minus ? -num : num;
					}
					b = readByte();
				}
			}
	
			char[][] nextMatrix(int n, int m) {
				char[][] map = new char[n][];
				for (int i = 0; i < n; i++)
					map[i] = next(m);
				return map;
			}
	
			int[] nextIntArray(int n) {
				int[] a = new int[n];
				for (int i = 0; i < n; i++)
					a[i] = nextInt();
				return a;
			}
	
			long[] nextLongArray(int n) {
				long[] a = new long[n];
				for (int i = 0; i < n; i++)
					a[i] = nextLong();
				return a;
			}
	
			int[][] next2DInt(int n, int m) {
				int[][] arr = new int[n][];
				for (int i = 0; i < n; i++) {
					arr[i] = nextIntArray(m);
				}
				return arr;
			}
	
			long[][] next2DLong(int n, int m) {
				long[][] arr = new long[n][];
				for (int i = 0; i < n; i++) {
					arr[i] = nextLongArray(m);
				}
				return arr;
			}
	
			int[] shuffle(int[] arr) {
				Random r = new Random();
				for (int i = 1, j; i < arr.length; i++) {
					j = r.nextInt(i);
					int c = arr[i];
					arr[i] = arr[j];
					arr[j] = c;
				}
				return arr;
			}
	
			long[] shuffle(long[] arr) {
				Random r = new Random();
				for (int i = 1, j; i < arr.length; i++) {
					j = r.nextInt(i);
					long c = arr[i];
					arr[i] = arr[j];
					arr[j] = c;
				}
				return arr;
			}
	
			int[] uniq(int[] arr) {
				arr = scn.shuffle(arr);
				Arrays.sort(arr);
				int[] rv = new int[arr.length];
				int pos = 0;
				rv[pos++] = arr[0];
				for (int i = 1; i < arr.length; i++) {
					if (arr[i] != arr[i - 1]) {
						rv[pos++] = arr[i];
					}
				}
				return Arrays.copyOf(rv, pos);
			}
	
			long[] uniq(long[] arr) {
				arr = scn.shuffle(arr);
				Arrays.sort(arr);
				long[] rv = new long[arr.length];
				int pos = 0;
				rv[pos++] = arr[0];
				for (int i = 1; i < arr.length; i++) {
					if (arr[i] != arr[i - 1]) {
						rv[pos++] = arr[i];
					}
				}
				return Arrays.copyOf(rv, pos);
			}
	
			int[] reverse(int[] arr) {
				int l = 0, r = arr.length - 1;
				while (l < r) {
					arr[l] = arr[l] ^ arr[r];
					arr[r] = arr[l] ^ arr[r];
					arr[l] = arr[l] ^ arr[r];
					l++;
					r--;
				}
				return arr;
			}
	
			long[] reverse(long[] arr) {
				int l = 0, r = arr.length - 1;
				while (l < r) {
					arr[l] = arr[l] ^ arr[r];
					arr[r] = arr[l] ^ arr[r];
					arr[l] = arr[l] ^ arr[r];
					l++;
					r--;
				}
				return arr;
			}
	
			int[] compress(int[] arr) {
				int n = arr.length;
				int[] rv = Arrays.copyOf(arr, n);
				rv = uniq(rv);
				for (int i = 0; i < n; i++) {
					arr[i] = Arrays.binarySearch(rv, arr[i]);
				}
				return arr;
			}
	
			long[] compress(long[] arr) {
				int n = arr.length;
				long[] rv = Arrays.copyOf(arr, n);
				rv = uniq(rv);
				for (int i = 0; i < n; i++) {
					arr[i] = Arrays.binarySearch(rv, arr[i]);
				}
				return arr;
			}
		}
	}