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 {

//	static long offset = 1000000000;
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		n = sc.nextInt();
		g = new ArrayList[n];
		for(int i = 0; i < n; i++) g[i] = new ArrayList<>();
		for(int i = 0; i < n-1; i++) {
			int u = sc.nextInt()-1;
			int v = sc.nextInt()-1;
			g[u].add(v);
			g[v].add(u);
		}
		leaf = new boolean[n];
		int countleaves = 0;
		for(int i = 0; i < n; i++) {
			if(g[i].size() == 1) {
				countleaves++;
				leaf[i] = true;
			}
		}
		if(countleaves == n-1) {//is star
			System.out.println("1 1");
		}
		else {
			int sameyleaves = 0;
			for(int i = 0; i < n; i++) {
				int lvs = 0;
				for(int u: g[i]) {
					if(leaf[u]) lvs++;
				}
				if(lvs > 1)
					sameyleaves += lvs-1;
			}
			depth = new int[n];
			dfs1(0, -1);
			boolean res = dfs2(0, -1);
			int a = res ? 3 : 1;
			int b = n - 1 - sameyleaves;
			System.out.println(a+" "+b);
		}
		
	}
	static boolean[] leaf;
	static int n;
	static ArrayList<Integer>[] g;
	static int[] depth;
	static int dfs1(int u, int p) {
		int maxd = 0; 
		for(int v: g[u]) {
			if(v == p) continue;
			int d = dfs1(v, u);
			if(d+1 > maxd) maxd = d+1;
		}
		return depth[u] = maxd;
	}
	static boolean dfs2(int u, int p) {
		int check = 0;
		for(int v: g[u]) {
			if(v == p) continue;
			if(dfs2(v, u)) return true;
			if(depth[v] % 2 == 0) check |= 1;
			else if(depth[v] % 2 == 1) check |= 2;
		}
		if(p == -1 && leaf[u] && check == 1) return true; 
		if(check == 3) return true;
		return false;
	}
	
	static class FastScanner {
		public BufferedReader reader;
		public StringTokenizer tokenizer;
		public FastScanner() {
			reader = new BufferedReader(new InputStreamReader(System.in), 32768);
			tokenizer = null;
		}
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch(IOException e) {
				throw new RuntimeException(e);
			}
		}
	}


}
