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<cstdio>
#include<vector>
#include<algorithm>
std::vector<int>g[100005];
int in[100005];
int cntA[100005];
int parent[100005];
int depth[100005];
int seq[100005];
int t[100005];
int bad[100005];
int order[100005];
int total = 0;

void dfs(int u,int have){
    order[++total] = u;
    int need = in[u]-have;
    if(u!=1) need--;
    if(need<0) need = 0;
    //printf("u = %d: %d\n",u,need);
    cntA[u] = need/2+need%2;
    for(int v: g[u]){ 
        if(parent[v]!=0) continue;
        parent[v] = u;
        dfs(v,1);
    }
}

int isGood(int n,int upper){
    if(n%2){ 
        if(t[n]>upper) return 0;
        return isGood(n-1,upper);
    }
    else{
        for(int i = 1; i <= n/2; i++){
            if(t[i]+t[n-i+1]>upper) return 0;
        }
        return 1;
    }
}

void dp(int u,int upper){
    bad[u] = 0;
    if(in[u]==1){ 
        depth[u] = 0;
        return ;
    }
    int size = 0;
    for(int v: g[u]){
        if(parent[v]==u) seq[++size] = depth[v]+1;
    }
    std::sort(seq+1,seq+1+size);
    if(in[u]%2){
        for(int i = 1; i <= size; i++) t[i] = seq[i];
        if(isGood(size,upper)) depth[u] = 0;
        else{
            int L = 1, R = size;
            int res = -1;
            while(L<=R){
                int M = (L+R)/2;
                int tSize = 0;
                for(int i = 1; i <= size; i++) if(i!=M) t[++tSize] = seq[i];
                if(isGood(tSize,upper)){
                    res = M;
                    R = M-1;
                } 
                else L = M+1;
            }
            if(res==-1){
                bad[u] = 1;
                return ;
            }
            else{
                depth[u] = seq[res];
            }
        }
    }
    else{
        int L = 1, R = size;
        int res = -1;
        while(L<=R){
            int M = (L+R)/2;
            int tSize = 0;
            for(int i = 1; i <= size; i++) if(i!=M) t[++tSize] = seq[i];
            if(isGood(tSize,upper)){
                res = M;
                R = M-1;
            } 
            else L = M+1;
        }
        if(res==-1){
            bad[u] = 1;
            return ;
        }
        else{
            depth[u] = seq[res];
        }
    }
}

int isOk(int s,int n,int upper){
    for(int i = n; i >= 2; i--){
        int u = order[i];
        dp(u,upper);
        if(bad[u]) return 0;
        //else printf("depth[%d] = %d\n",u,depth[u]);
    }
    int size = 0;
    for(int v: g[s]){
        seq[++size] = depth[v]+1;
    }
    std::sort(seq+1,seq+1+size);
    for(int i = 1; i <= size; i++) t[i] = seq[i];
    if(isGood(size,upper)) return 1;
    else return 0;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n-1; i++){
        int u,v;
        scanf("%d%d",&u,&v);
        in[u]++, in[v]++;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    parent[1] = -1;
    dfs(1,0);
    int ansA = 0;
    for(int i = 1; i <= n; i++) ansA += cntA[i];
    int L = 1, R = n;
    int ansB = -1;
    while(L<=R){
        int M = (L+R)/2;
        if(isOk(1,n,M)){
            ansB = M;
            R = M-1;
        }
        else L = M+1;
    }
    //int ansB = isOk(1,n,4);
    printf("%d %d\n",ansA,ansB);
    return 0;
}