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>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<vector<Int> > G(n);
  for(Int i=1;i<n;i++){
    Int a,b;
    cin>>a>>b;
    a--;b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  {
    Int A=0;
    for(Int i=0;i<n;i++)
      A+=G[i].size()&1;
    cout<<A/2<<" ";
  }

  auto check=
    [&](Int x)->Int{
      Int ng=0;
      function<Int(Int, Int)> dfs=
        [&](Int v,Int p)->Int{
          vector<Int> vs;
          for(Int u:G[v]){
            if(u==p) continue;            
            vs.emplace_back(dfs(u,v)+1);
          }
          
          if(G[v].size()&1)
            vs.emplace_back(0);
          sort(vs.begin(),vs.end());
          
          Int k=vs.size();
          if(p<0){
            assert(~k&1);
            for(Int i=0;i<k/2;i++)
              if(vs[i]+vs[k-(i+1)]>x) return ng=1;
            return 0;
          }
          
          assert(k&1);
          
          auto check2=
            [&](Int y)->Int{
              vector<Int> us;
              for(Int i=0;i<k;i++)
                if(i!=y) us.emplace_back(vs[i]);
              Int l=us.size();
              assert(~l&1);
              for(Int i=0;i<l/2;i++)
                if(us[i]+us[l-(i+1)]>x) return 0;
              return 1;
            };
          
          Int l=-1,r=k;
          while(l+1<r){
            Int m=(l+r)>>1;
            if(check2(m)) r=m;
            else l=m;
          }
          if(r==k) return ng=1;
          return vs[r];
        };
      
      dfs(0,-1);
      return !ng;
    };
    
  Int l=0,r=n;
  while(l+1<r){
    Int m=(l+r)>>1;
    if(check(m)) r=m;
    else l=m;
  }
  cout<<r<<endl;
  return 0;
}