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;

#define N 300000

int n,x,y,ans,l,r,mid,tot,rt,f[N],a[N],g[N],head[N],d[N];
struct edge{int v,nxt;}e[N];

void add(int x,int y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}

bool dp(int u,int fa){
    f[u]=0;
    for (int i=head[u],v;i;i=e[i].nxt)
        if ((v=e[i].v)!=fa) if (!dp(v,u)) return 0;
    //printf("+++++++%d+++++++\n",u);
    //for (int i=head[u],v;i;i=e[i].nxt)
        //if ((v=e[i].v)!=fa) printf("%d\n",f[v]);
    int xb=0;
    for (int i=head[u],v;i;i=e[i].nxt)
        if ((v=e[i].v)!=fa) a[++xb]=f[v]+1;
    if ((xb&1)==0) a[++xb]=0;
    sort(a+1,a+xb+1);//for (int i=1;i<=xb;i++) cout<<a[i]<<endl;
    memset(g,-1,sizeof(int)*(xb+2));
    int j,k; j=1;
    for (int i=xb;i>=1;i--){
        g[i]=g[i+1];//if (j>=i) g[i]=i-1;
        for (;j<i && a[j]+a[i]<=mid;j++) g[i]=j;
        j--;
    }
    j=0,k=0;
    for (int i=xb;i>xb/2+1;i--) if (g[i]<xb-i+1){k=i; break;}//cout<<"orz"<<k<<endl;
    if (k==0){
        j=1; for (int i=xb;i>xb/2+1;i--) if (g[i]<xb-i+2) j=xb-i+2;
        f[u]=a[j];
    }
    else{
        j=0; for (int i=xb;i>j+1;i--) if (k!=i){j++; if (a[i]+a[j]>mid) return 0;}
        f[u]=a[k];
    }
    if (u==rt && f[u]>mid) return 0;
    return 1;
}

int main(){//freopen("in","r",stdin);
    scanf("%d",&n);
    for (int i=1;i<n;i++){scanf("%d%d",&x,&y); add(x,y); add(y,x); d[x]++; d[y]++;}
    for (int i=1;i<=n;i++) if (d[i]&1) ans++;
    for (int i=1;i<=n;i++) if (d[i]==1){rt=i; break;}// cout<<rt<<endl;
    ans/=2; printf("%d ",ans);
    l=1,r=n;
    while (l<=r){
        mid=(l+r)>>1; memset(f,0,sizeof f);
        if (dp(rt,0)){ans=mid; r=mid-1;} else l=mid+1;
    }//*/mid=2; if (dp(rt,0)) puts("orz");
    printf("%d\n",ans);

    return 0;
}