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;
const int maxn=100100;
int beg[maxn],tto[maxn<<1],nex[maxn<<1],e;
void putin(int s,int t){
	tto[++e]=t;
	nex[e]=beg[s];
	beg[s]=e;
}
int dfsA(int u,int fa){
	int res=0,cnt=0;
	for(int i=beg[u];i;i=nex[i]){
		if(tto[i]==fa) continue;
		res+=dfsA(tto[i],u);
		cnt++;
	}
	if(fa==-1) res+=(cnt+1)/2;
	else res+=cnt/2;
	return res;
}
int B,bo;
multiset<int> sak[maxn];
multiset<int>::iterator it,itt;
int n;
int dfsB(int u,int fa){
	int v;
	for(int i=beg[u];i;i=nex[i]){
		if(tto[i]==fa) continue;
		v=dfsB(tto[i],u)+1;
		if(v>B){
			bo=0;
			return 0;
		}
		sak[u].insert(v);
		if(!bo) return 0;
	}
	int res=sak[u].size()&1?1:2,vl=0;
	if(fa==-1) res=sak[u].size()&1?1:0;
	while(!sak[u].empty()){
		itt=sak[u].end();
		itt--;
		v=*itt;
		it=sak[u].upper_bound(B-v);
		if(it==sak[u].begin()||(int)sak[u].size()==1){
			if(!res){
				bo=0;
				return 0;
			}
			res--;
			sak[u].erase(itt);
			vl=v;
			continue;
		}
		it--;
		if(it==itt) it--;
		sak[u].erase(it);
		itt=sak[u].end();
		itt--;
		sak[u].erase(itt);
	}
	return vl;
}
bool solve(int x){
	B=x,bo=1;
	for(int i=1;i<=n;i++)
		sak[i].clear();
	dfsB(1,-1);
	return bo;
}
int main(){
//	freopen("A.in","r",stdin);
//	freopen("A.out","w",stdout);
	scanf("%d",&n);
	int s,t;
	for(int i=1;i<n;i++){
		scanf("%d%d",&s,&t);
		putin(s,t);
		putin(t,s);
	}
	int A=dfsA(1,-1);
	int l=0,r=n,mid;
	while(r-l>1){
		mid=(l+r)>>1;
		if(solve(mid)) r=mid;
		else l=mid;
	}
	printf("%d %d\n",A,r);
	return 0;
}