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.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public final class Main
{
	static long mod = 998244353l;
	static Map<Long, Long> invk = new HashMap<>();
	static int f[];
	static int fmin = 0;

	static List<Integer> leafs = new ArrayList<>();
	static int[] depth;
	static int[] nbleaf;
	static boolean[] vis;

	public static void main(String[] args) throws IOException
	{
		Scanner in = getScan(args);
		// int tt = in.nextInt();
		// while (tt-- > 0)
		// {
		int n = in.nextInt();
		depth = new int[n];
		vis = new boolean[n];
		nbleaf = new int[n];
		List<Integer> 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 = in.nextInt() - 1;
			int v = in.nextInt() - 1;
			g[u].add(v);
			g[v].add(u);
		}

		dfs(g, 0, 0);
		int par = depth[leafs.get(0)] % 2;
		boolean samepar = true;
		for (int l : leafs)
		{
			if (depth[l] % 2 != par)
			{
				samepar = false;
				break;
			}
		}
		int min = samepar ? 1 : 3;
		int max = n - 1;
		int sum = 0;
		for (int i = 0; i < n; i++)
		{
			if (nbleaf[i] > 1)
			{
				sum += nbleaf[i] - 1;
			}
		}
		max -= sum;
		System.out.println(min + " " + max);
		// }
	}

	public static void dfs(List<Integer> g[], int node, int d)
	{
		vis[node] = true;
		depth[node] = d;
		if (g[node].size() == 1)
		{
			leafs.add(node);
			nbleaf[g[node].get(0)]++;
		}
		for (int i : g[node])
		{
			if (!vis[i])
			{
				dfs(g, i, d + 1);
			}
		}
	}

	public static long gcd(long a, long b, Pair p)
	{
		long x = 1, y = 0, x1 = 0, y1 = 1, a1 = a, b1 = b;

		while (b1 > 0)
		{
			long q = a1 / b1;
			long tmp = x - q * x1;
			x = x1;
			x1 = tmp;
			tmp = y - q * y1;
			y = y1;
			y1 = tmp;
			tmp = a1 - q * b1;
			a1 = b1;
			b1 = tmp;
		}
		p.first = x;
		p.second = y;
		return a1;
	}

	public static class Pair
	{
		public long first;
		public long second;
	}

	public static long gcd(long a, long b)
	{
		if (a == 0 || b == 0)
		{
			return a | b;
		}
		int shift = Long.numberOfTrailingZeros(a | b);
		a = a >> Long.numberOfTrailingZeros(a);
		while (b > 0)
		{
			b = b >> Long.numberOfTrailingZeros(b);
			if (a > b)
			{
				long tmp = a;
				a = b;
				b = tmp;
			}
			b -= a;
		}
		return a << shift;
	}

	public static int find(Subset[] subset, int i)
	{
		if (subset[i].parent != i)
		{
			subset[i].parent = find(subset, subset[i].parent);
		}
		return subset[i].parent;
	}

	public static void union(Subset[] subset, int x, int y)
	{
		int rootx = find(subset, x);
		int rooty = find(subset, y);
		if (subset[rootx].rank < subset[rooty].rank)
		{
			subset[rootx].parent = rooty;
		}
		else if (subset[rootx].rank > subset[rooty].rank)
		{
			subset[rooty].parent = rootx;
		}
		else
		{
			subset[rootx].parent = rooty;
			subset[rooty].rank++;
		}
	}

	static class Subset
	{
		int parent;
		int rank;
	}

	public static long fact(int n)
	{
		if (n <= fmin)
		{
			return f[n];
		}
		long res = f[fmin];
		for (int i = fmin + 1; i <= n; i++)
		{
			res = (res * i) % mod;
			f[i] = (int) res;
		}
		fmin = n;
		return res;
	}

	public static int log2nlz(int bits)
	{
		if (bits == 0) return 0; // or throw exception
		return 31 - Integer.numberOfLeadingZeros(bits);
	}

	static Scanner getScan(String[] args) throws IOException
	{
		if (args.length == 0)
		{
			return new Scanner(System.in);
		}
		else
		{
			return new Scanner(new File(args[0]));
		}
	}

	static BufferedReader getBuffer(String[] args) throws IOException
	{
		if (args.length == 0)
		{
			return new BufferedReader(new InputStreamReader(System.in));
		}
		else
		{
			return new BufferedReader(new FileReader(args[0]));
		}
	}

	public static long binpowMod(long x, long y, long mod)
	{
		long z = 1;
		x = x % mod;
		while (y > 0)
		{
			if (y % 2 == 1)
			{
				z = (z * x) % mod;
				y--;
			}
			else
			{
				x = (x * x) % mod;
				y = y >> 1;
			}
		}
		return z;
	}

	public static long invMod(long x, long mod)
	{
		if (!invk.containsKey(x))
		{
			invk.put(x, binpowMod(x, mod - 2, mod));
		}
		return invk.get(x);
	}

	public static long divMod(long x, long y, long mod)
	{
		x = x % mod;
		y = y % mod;
		return (x * invMod(y, mod)) % mod;
	}
}