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;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
typedef complex<D> P;
#define F first
#define S second
const ll MOD=1000000007;
//const ll MOD=998244353;

template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,const pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,const vector<T> &A){ll i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}

ll N;
vector<vector<ll>> edge;
vector<ll> ord;
ll m;
bool jd;

bool judge(ll sz,ll used,const vector<ll> &beet){
  for(int i=0;2*i+2<sz;i++){
    ll lf=(i>=used?beet[i+1]:beet[i]);
    ll rg=((sz-i-2)>=used?beet[sz-i-2+1]:beet[sz-i-2]);
    if(lf+rg+1>m){return false;}
  }
  return true;
}

ll dfs(ll u,ll p){
  vector<ll> beet(ord[u]+1);
  ll sz=0;
  for(auto &v:edge[u]){
    if(v!=p){
      beet[sz++]=dfs(v,u);
    }
  }
  sort(beet.begin(),beet.begin()+sz,greater<ll>());
  if((sz&1)==0){
    beet[sz++]=0;
    if(p==-1){jd&=judge(sz,sz-1,beet); return 0;}
  }
  ll lf=0,rg=sz;
  while(rg-lf>1){
    ll mid=(lf+rg)>>1;
    if(judge(sz,mid,beet)){lf=mid;}
    else{rg=mid;}
  }
  jd&=judge(sz,lf,beet);
  jd&=(beet[lf]+1<=m);
  return beet[lf]+1;
}

bool judge2(ll mid){
  m=mid;
  jd=true;
  dfs(0,-1);
  return jd;
}

int main(){
  cin>>N;
  edge.resize(N);
  ord.resize(N,0);

  for(int i=1;i<N;i++){
    ll a,b;
    cin>>a>>b;
    a--; b--;
    edge[a].push_back(b);
    edge[b].push_back(a);
    ord[a]++;
    ord[b]++;
  }

  ll cnt=0;
  for(auto &I:ord){cnt+=(I-1)/2;}
  
  ll l=0,r=N;
  while(r-l>1){
    ll mid=(l+r)>>1;
    if(judge2(N-mid)){l=mid;}
    else{r=mid;}
  }
  cout<<cnt+1<<" "<<N-l-1<<endl;

  return 0;
}