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.util.*;
import java.io.*;
public class Main {
    static class Scan {
        private byte[] buf=new byte[1024];
        private int index;
        private InputStream in;
        private int total;
        public Scan()
        {
            in=System.in;
        }
        public int scan()throws IOException
        {
            if(total<0)
            throw new InputMismatchException();
            if(index>=total)
            {
                index=0;
                total=in.read(buf);
                if(total<=0)
                return -1;
            }
            return buf[index++];
        }
        public int scanInt()throws IOException
        {
            int integer=0;
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            int neg=1;
            if(n=='-')
            {
                neg=-1;
                n=scan();
            }
            while(!isWhiteSpace(n))
            {
                if(n>='0'&&n<='9')
                {
                    integer*=10;
                    integer+=n-'0';
                    n=scan();
                }
                else throw new InputMismatchException();
            }
            return neg*integer;
        }
        public double scanDouble()throws IOException
        {
            double doub=0;
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            int neg=1;
            if(n=='-')
            {
                neg=-1;
                n=scan();
            }
            while(!isWhiteSpace(n)&&n!='.')
            {
                if(n>='0'&&n<='9')
                {
                    doub*=10;
                    doub+=n-'0';
                    n=scan();
                }
                else throw new InputMismatchException();
            }
            if(n=='.')
            {
                n=scan();
                double temp=1;
                while(!isWhiteSpace(n))
                {
                    if(n>='0'&&n<='9')
                    {
                        temp/=10;
                        doub+=(n-'0')*temp;
                        n=scan();
                    }
                    else throw new InputMismatchException();
                }
            }
            return doub*neg;
        }
        public String scanString()throws IOException
        {
            StringBuilder sb=new StringBuilder();
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            while(!isWhiteSpace(n))
            {
                sb.append((char)n);
                n=scan();
            }
            return sb.toString();
        }
        private boolean isWhiteSpace(int n)
        {
            if(n==' '||n=='\n'||n=='\r'||n=='\t'||n==-1)
            return true;
            return false;
        }
    }
    static ArrayList<Integer> adj_lst[];
    static int ans_min,ans_max;
    public static void main(String args[]) throws IOException {
        Scan input=new Scan();
        int n=input.scanInt();
        adj_lst=new ArrayList[n];
        for(int i=0;i<n;i++) {
            adj_lst[i]=new ArrayList<>();
        }
        for(int i=0;i<n-1;i++) {
            int u=input.scanInt()-1;
            int v=input.scanInt()-1;
            adj_lst[u].add(v);
            adj_lst[v].add(u);
        }
        ans_min=1;
        ans_max=adj_lst.length-1;
        int root=-1;
        for(int i=0;i<n;i++) {
            if(adj_lst[i].size()>1) {
                root=i;
                break;
            }
        }
        DFS(root,-1);
        count(root,-1);
        System.out.println(ans_min+" "+ans_max);
    }
    public static int[] DFS(int root,int par) { //{odd,even}
        if(adj_lst[root].size()==1) {
            return new int[]{0,1};
        }
        int even=0,odd=0;
        for(int i=0;i<adj_lst[root].size();i++) {
            if(adj_lst[root].get(i)!=par) {
                int tmp[]=DFS(adj_lst[root].get(i),root);
                even+=tmp[0];
                odd+=tmp[1];
            }
        }
//        if(even==1 && odd==1) {
//            ans_min=Math.max(ans_min, 2);
//        }
        if(even>=1 && odd>=1) {
            ans_min=Math.max(ans_min,3);
        }
        return new int[]{odd,even};
    } 
    public static int count(int root,int par) {
        if(adj_lst[root].size()==1) {
            return 1;
        }
        int cnt=0;
        for(int i=0;i<adj_lst[root].size();i++) {
            if(adj_lst[root].get(i)!=par) {
                cnt+=count(adj_lst[root].get(i),root);
            }
        }
        if(cnt>1) {
            ans_max-=(cnt-1);
        }
        return 0;
    }
}
