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 <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define ref(i,x,y)for(int i=x;i<=y;++i)
#define def(i,x,y)for(int i=x;i>=y;--i)
const int N=100001;
int n,cnt,head[N],du[N];
struct xint{int to,next;}e[N*2];
void addedge(int x,int y){
	e[++cnt]=(xint){y,head[x]};head[x]=cnt;
	e[++cnt]=(xint){x,head[y]};head[y]=cnt;
	du[x]++;du[y]++;
}
int Mid,p[N],f[N],a[N];
int top,stk[N];bool mk[N];
bool Check(){
	ref(i,1,p[0])mk[i]=0;
	int pos=1;top=0;
	def(i,p[0],1)if(!mk[i]){
		if(pos>i)pos=i;
		while(top>0&&stk[top]>=i)top--;
		while(pos<i&&p[pos]+p[i]<=Mid)stk[++top]=pos,pos++;
		if(!top)return 0;
		mk[stk[top]]=1;top--;mk[i]=1;
	}
	return 1;
}
bool check(int x){
	a[0]=0;
	ref(i,1,p[0])if(i!=x)a[++a[0]]=p[i];
	if(a[0]&1)a[0]--;
	ref(i,1,a[0])mk[i]=0;
	int pos=1;top=0;
	def(i,a[0],1)if(!mk[i]){
		if(pos>i)pos=i;
		while(top>0&&stk[top]>=i)top--;
		while(pos<i&&a[pos]+a[i]<=Mid)stk[++top]=pos,pos++;
		if(!top)return 0;
		mk[stk[top]]=1;top--;mk[i]=1;
	}
	return 1;
}
void dfs(int fa,int x){
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;if(y==fa)continue;dfs(x,y);
	}
	p[0]=0;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;if(y==fa)continue;
		p[++p[0]]=f[y]+1;
		if(p[p[0]]>Mid){f[x]=1e9;return;}
	}
	if(!p[0]){f[x]=0;return;}
	sort(p+1,p+p[0]+1);
	if(x==1&&!(p[0]&1)){
		if(!Check())f[x]=1e9;else f[x]=0;
		return;
	}
	if(!(p[0]&1)&&Check()){f[x]=0;return;}
	int l=1,r=p[0]+1;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid))r=mid;else l=mid+1;
	}
	if(l==p[0]+1){f[x]=1e9;return;}
	f[x]=p[l];
}
int main(){
	scanf("%d",&n);
	ref(i,2,n){
		int x,y;
		scanf("%d%d",&x,&y);
		addedge(x,y);
	}
	int tot=0;
	ref(i,1,n)if(du[i]&1)tot++;
	cout<<tot/2<<" ";
	int L=1,R=n-1;
	while(L<R){
		memset(f,0,sizeof f);
		Mid=(L+R)>>1;
		dfs(0,1);
		if(f[1]<=Mid)R=Mid;else L=Mid+1;
	}
	cout<<L<<endl;
}