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.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Practice {
	public static long mod = (long) Math.pow(10, 9) + 7;
	public static long mod2 = 998244353;
	public static long tt = 0;
	public static int[] ttt = new int[2];
	public static long[] fac = new long[500000];
	public static ArrayList<Integer> prime;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);

		// int t = Integer.parseInt(br.readLine());
		// while (t-- > 0) {
		String[] s1 = br.readLine().split(" ");
		int n = Integer.parseInt(s1[0]);
		HashMap[] edg = new HashMap[n + 1];
		for (int i = 0; i <= n; i++) {
			edg[i] = new HashMap<Integer, Integer>();
		}
		for (int i = 1; i < n; i++) {
			String[] s2 = br.readLine().split(" ");
			int u = Integer.parseInt(s2[0]);
			int v = Integer.parseInt(s2[1]);
			edg[u].put(v, 1);
			edg[v].put(u, 1);
		}
		int min = 1;

		int[] done = new int[n + 1];
		int x = getAns(1, edg, n, done);
		if (x == 3 || (x == 2 && edg[1].size() == 1)) {
			min = 3;
		}
//		for (int i = 0; i <= n; i++) {
//			System.out.print(done[i] + " ");
//		}
//		System.out.println();
		done = new int[n + 1];
		tt = 0;

		getAb(1, edg, n, done);
//		for (int i = 0; i <= n; i++) {
//			System.out.print(done[i] + " ");
//		}
//		System.out.println();
		pw.println(min + " " + (n - 1 - tt));
		// }

		pw.close();

	}

	private static int[] getAb(int i, HashMap[] edg, int n, int[] done) {
		// TODO Auto-generated method stub
		done[i] = 1;
		ArrayList<Integer> list = new ArrayList<Integer>(edg[i].keySet());
		// System.out.println(list+" "+tt);
		int curr = 0;
		int b = 0;
		int ttt = 0;
		// int[] arr = new int[3];
		for (int a : list) {
			if (done[a] == 0) {
				b = 1;
				int[] c = getAb(a, edg, n, done);
				curr += c[0];
				ttt += c[1];
			}
		}
		// System.out.println(curr + " " + ttt + " " + i);
		// done[i] = curr - 1;
		if (curr - 1 > 0) {
			tt += curr - 1;
		}
		// System.out.println(tt);
		if (list.size() == 1) {
			if (ttt == 1) {
				tt += ttt;
			} else if (ttt > 0) {
				tt += 1;
			}

			// done[i] = 1;
			int[] ret = new int[2];
			ret[0] = 1;
			return ret;
		}
		int[] ret = new int[2];
		ret[1] = curr;
		return ret;
	}

	private static int getAns(int i, HashMap[] edg, int n, int[] done) {
		// TODO Auto-generated method stub
		done[i] = 1;
		ArrayList<Integer> list = new ArrayList<Integer>(edg[i].keySet());
		// System.out.println(i);
		int curr = 0;
		for (int a : list) {
			if (done[a] == 0) {
				int c = getAns(a, edg, n, done);
				if (c == 3) {
					return c;
				}
				curr = curr | c;
			}
		}
		if (curr == 0) {
			done[i] = 1;
			return 1;
		}
		done[i] = curr;
		if (curr == 3) {
			return curr;
		} else {
			done[i] = curr ^ 3;
			return curr ^ (3);
		}
	}

}

//	private static void getFac(long n, PrintWriter pw) {
//		// TODO Auto-generated method stub
//		int a = 0;
//		while (n % 2 == 0) {
//			a++;
//			n = n / 2;
//		}
//		if (n == 1) {
//			a--;
//		}
//		for (int i = 3; i <= Math.sqrt(n); i += 2) {
//			while (n % i == 0) {
//				n = n / i;
//				a++;
//			}
//		}
//		if (n > 1) {
//			a++;
//		}
//		if (a % 2 == 0) {
//			pw.println("Bob");
//		} else {
//			pw.println("Alice");
//		}
//		//System.out.println(a);
//		return;
//	}

//	private static long power(long a, long p) {
//		// TODO Auto-generated method stub
//		long res = 1;
//		while (p > 0) {
//			if (p % 2 == 1) {
//				res = (res * a) % mod;
//			}
//			p = p / 2;
//			a = (a * a) % mod;
//		}
//		return res;
//	}
//
//	private static void fac() {
//		fac[0] = 1;
//		// TODO Auto-generated method stub
//		for (int i = 1; i < fac.length; i++) {
//			if (i == 1) {
//				fac[i] = 1;
//			} else {
//				fac[i] = i * fac[i - 1];
//			}
//			if (fac[i] > mod) {
//				fac[i] = fac[i] % mod;
//			}
//		}
//	}
//
//	private static int getLower(Long long1, Long[] st) {
//		// TODO Auto-generated method stub
//		int left = 0, right = st.length - 1;
//		int ans = -1;
//		while (left <= right) {
//			int mid = (left + right) / 2;
//			if (st[mid] <= long1) {
//				ans = mid;
//				left = mid + 1;
//			} else {
//				right = mid - 1;
//			}
//		}
//		return ans;
//	}

//	private static long getGCD(long l, long m) {
//
//		long t1 = Math.min(l, m);
//		long t2 = Math.max(l, m);
//		while (true) {
//			long temp = t2 % t1;
//			if (temp == 0) {
//				return t1;
//			}
//			t2 = t1;
//			t1 = temp;
//		}
//	}