Problem: Takahashi has decided to make a Christmas Tree for the Christmas party in AtCoder, Inc.

A Christmas Tree is a tree with N vertices numbered 1 through N and N-1 edges, whose i-th edge (1\leq i\leq N-1) connects Vertex a_i and b_i.

He would like to make one as follows:

* Specify two non-negative integers A and B.
* Prepare A Christmas Paths whose lengths are at most B. Here, a Christmas Path of length X is a graph with X+1 vertices and X edges such that, if we properly number the vertices 1 through X+1, the i-th edge (1\leq i\leq X) will connect Vertex i and i+1.
* Repeat the following operation until he has one connected tree:
* Select two vertices x and y that belong to different connected components. Combine x and y into one vertex. More precisely, for each edge (p,y) incident to the vertex y, add the edge (p,x). Then, delete the vertex y and all the edges incident to y.
* Properly number the vertices in the tree.



Takahashi would like to find the lexicographically smallest pair (A,B) such that he can make a Christmas Tree, that is, find the smallest A, and find the smallest B under the condition that A is minimized.

Solve this problem for him.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq a_i,b_i \leq N
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}


Output

For the lexicographically smallest (A,B), print A and B with a space in between.

Examples

Input

7
1 2
2 3
2 4
4 5
4 6
6 7


Output

3 2


Input

8
1 2
2 3
3 4
4 5
5 6
5 7
5 8


Output

2 5


Input

10
1 2
2 3
3 4
2 5
6 5
6 7
7 8
5 9
10 5


Output

3 4

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define pi 3.1415926535897932384626
using namespace std;
      
struct P{
  int x,y;
  bool operator < (const P &a )const{
    //if(y!=a.y)
    return y<a.y;
  };
};

int a,b,c,d,i,k,n,m,e,dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1};
int o[100111];
int l[100101];
int j[1];

long long x,y,z,mod=1000000007;
//string r;
char r[1];

P u[1];
queue<int> q;
stack<int> s;

vector<int> v[100101];

bool as(P a,P b)
{
  return a.x>b.x;
}
void f(int n,int m)
{
  vector<int> s;
  for(int h=0;h<v[n].size();h++)
  if(v[n][h]!=m)
  {
    f(v[n][h],n);
    s.push_back(l[v[n][h]]+1);
  }
  if((s.size()%2==0&&m>0)||(s.size()%2&&m==0)) s.push_back(0);
  sort(s.begin(),s.end());
  
  if(m==0)
  {
    int c=0,d=s.size()-1;
    o[n]=0;
    for(;c<d;c++,d--)
    o[n]=max(o[n],s[c]+s[d]);
    return;
  }
  int a=0,b=s.size()-1;
  for(;a<b;)
  {
    int h=(a+b)/2;
    int x=0,c=0,d=s.size()-1;
    for(;c<d;)
    if(c==h) c++;
    else if(d==h) d--;
    else
    {
      x=max(x,s[c]+s[d]);
      c++,d--;
    }
    if(x<=k) b=h;
    else a=h+1;
  }
  l[n]=s[a];
  int x=0,c=0,d=s.size()-1;
  for(;c<d;)
  if(c==a) c++;
  else if(d==a) d--;
  else
  {
    x=max(x,s[c]+s[d]);
    c++,d--;
  }
  o[n]=x;
}

int main()
{
  scanf("%d",&a);
  for(int t=1;t<a;t++)
  {
    scanf("%d %d",&n,&m);
    v[n].push_back(m);
    v[m].push_back(n);
  }
  for(int t=1;t<=a;t++)
    e+=v[t].size()%2;
  printf("%d ",e/2);
  n=1,m=a-1;
  for(;n<m;)
  {
    k=(n+m)/2;
    f(1,0);
    //for(int t=1;t<=a;t++)
    //  printf("%d ",o[t]);
    //puts("");
    for(int t=1;t<=a;t++)
      if(o[t]>k)
      {
        n=k+1;
        goto qwe;
      }
    m=k;
    qwe:;
  }
  printf("%d",n);
}