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 Sol{

static class Pair implements Comparable<Pair>{
        int x;int y;
        public Pair(int x,int y) {
         
          this.x=x;this.y=y;
        }
        @Override
        public int compareTo(Pair p){return Long.compare(y,p.y); }
       
   }

static int n;
static ArrayList<Integer> adj[];
static int leafchild[];static boolean oddlevel=false;static boolean evenlevel=false;
static void dfs(int u,int p,int level){
 
 for(int i:adj[u]){
   if(i==p)continue;
   dfs(i,u,level+1);
 } 
 if(adj[u].size()==1){leafchild[p]++;
       if(level%2==0)evenlevel=true;
       else oddlevel=true;
 }

}

public static void main(String []args){

int times=1;

while(times-->0){

n=ni();
adj=new ArrayList[n+1];leafchild=new int[n+1];
for(int i=1;i<=n;i++){adj[i]=new ArrayList<Integer>();}
for(int i=1;i<=n-1;i++){int u=ni();int v=ni();adj[u].add(v);adj[v].add(u);}
int i=1;
while(adj[i].size()==1)i++;
dfs(i,0,0);

int f1=1;int f2=n-1;

if(oddlevel && evenlevel)f1+=2;

for(i=1;i<=n;i++){if(leafchild[i]>0){f2=f2-leafchild[i]+1;}}

out.println(f1+" "+f2);

}out.close();}

//-----------------Utility--------------------------------------------

static long Comb[][]=new long[405][405];
static long p2[]=new long[405];
static long inv[]=new long[405];
static long factorial[]=new long[405];
static void precomp(){

inv[0]=1;factorial[0]=1l;

for(long i=1;i<405;i++){factorial[(int)i]=i*factorial[(int)i-1];factorial[(int)i]%=mod;}

for(int i=1;i<405;i++){ inv[i]=power(factorial[i],mod-2);}

for(int i=0;i<405;i++){
 
   for(int j=0;j<=i;j++){
     Comb[i][j]=(((factorial[i]*inv[j])%mod)*inv[i-j])%mod;
   }
 }

for(int i=0;i<405;i++)p2[i]=power(2,i);

}

static int Max=Integer.MAX_VALUE; static long mod=1000000007;
static int v(char c){return (int)(c-'a')+1;}
public static long power(long x, long y )
    {
        //0^0 = 1
        long res = 1L;
        x = x%mod;
        while(y > 0)
        {
            if((y&1)==1)
                res = (res*x)%mod;
            y >>= 1;
            x = (x*x)%mod;
        }
        return res;
    }
//--------------------------------------------------------------------

static InputStream inputStream = System.in;
static OutputStream outputStream = System.out;
static FastReader in=new FastReader(inputStream);
static PrintWriter out=new PrintWriter(outputStream);

static class FastReader 
{ 
  BufferedReader br; 
  StringTokenizer st; 
 
        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }
 
  public String next() 
  { 
      while (st == null || !st.hasMoreElements()) 
      { 
          try
          { 
              st = new StringTokenizer(br.readLine()); 
          } 
          catch (IOException  e) 
          { 
              e.printStackTrace(); 
          } 
      } 
      return st.nextToken(); 
  } 
 
  public int nextInt() 
  { 
      return Integer.parseInt(next()); 
  } 
 
  public long nextLong() 
  { 
      return Long.parseLong(next()); 
  } 
 
 public  double nextDouble() 
  { 
      return Double.parseDouble(next()); 
  } 
 
 
  String nextLine() 
  { 
      String str = ""; 
      try
      { 
          str = br.readLine(); 
      } 
      catch (IOException e) 
      { 
          e.printStackTrace(); 
      } 
      return str; 
  } 
}
static int ni(){return in.nextInt();}
static long nl(){return in.nextLong();}
static String ns(){return in.nextLine();}
static int[] na(int n){int a[]=new int[n];for(int i=0;i<n;i++){a[i]=ni();} return a;}

}