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 pair<int,int> pii;
typedef long long ll;
const int MAX=200040;
const ll MOD=1000000007;
vector<int> conn[MAX],dir[MAX],tmp[MAX];
int a,b,com=0,par[MAX],n;
void dfs(int x,int p){
    par[x]=p;
    for(int i=0;i<conn[x].size();i++) if(conn[x][i]!=p) dfs(conn[x][i],x);
}
int simple(int v,int u){
    int p1=1,p2=tmp[v].size()-1,pos=1;
    while(p1<p2){
        if(tmp[v][p1]+tmp[v][p2]>u) pos=0;
        p1++,p2--;
    }
    return pos;
}
int div2(int v,int x,int y,int u){
    if(y-x==1) return x;
    int p=(x+y)/2,p1=0,p2=tmp[v].size()-1,pos=1;
    //for(int i=p1;i<=p2;i++) printf("%d ",tmp[v][i]);
    if(p1==p) p1++;
    if(p2==p) p2--;
    while(p1<p2){
        if(tmp[v][p1]+tmp[v][p2]>u) pos=0;
        p1++,p2--;
        if(p1==p) p1++;
        if(p2==p) p2--;
    }
    if(pos) return div2(v,x,p,u);
    return div2(v,p,y,u);
}
int f(int x,int u){
    tmp[x].clear();
    if(dir[x].size()==0) return 0;
    if(dir[x].size()==1){
        int t=f(dir[x][0],u)+1;
        if(t==0||t>u) return -1;
        return t;
    }
    for(int i=0;i<dir[x].size();i++){
        int t=f(dir[x][i],u)+1;
        if(t==0) return -1;
        tmp[x].push_back(t);
    }
    if(tmp[x].size()%2==0) tmp[x].push_back(0);
    sort(tmp[x].begin(),tmp[x].end());
    int t=div2(x,0,tmp[x].size(),u)+1;
    if(tmp[x].size()==t) return -1;
    if(tmp[x][t]>u) return -1;
    if(simple(x,u)) return tmp[x][0];
    return tmp[x][t];
}
int div22(int x,int y){
    if(y-x==1) return x;
    int p=(x+y)/2,u=f(com,p);
    if(u==-1) return div22(p,y);
    return div22(x,p);
}
int main(){
    scanf(" %d",&n);
    for(int i=0;i<n-1;i++){
        int t1,t2;
        scanf(" %d %d",&t1,&t2);
        conn[t1].push_back(t2);
        conn[t2].push_back(t1);
    }
    for(int i=1;i<=n;i++) if(conn[i].size()%2) com=max(i,com), a+=1;
    a/=2;
    dfs(com,0);
    for(int i=1;i<=n;i++){
        for(int j=0;j<conn[i].size();j++) if(conn[i][j]!=par[i]) dir[i].push_back(conn[i][j]);
    }
    b=div22(0,n+1)+1;
    printf("%d %d\n",a,b);
}