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>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
int N;
vector<vector<int>> G;
int dfs(int v,int p,int L){
	multiset<int> ls,cls;
	for(int u:G[v]) if(u!=p){
		int tmp = dfs(u,v,L);
		if(tmp==-1) return -1;
		if(tmp>L) return -1;
		ls.insert(tmp);
	}
	cls = ls;
	int K = ls.size();

	if(K%2==0){
		{
			bool perfect = 1;
			vector<int> v;
			for(int x:ls) v.pb(x);
			rep(i,K/2) if(v[i]+v[K-1-i]>L) perfect = 0;
			if(perfect) return 1;
		}
		auto it = ls.end();
		it--;
		ls.erase(it);
	}

	int lef = -1;
	while(ls.size()>1){
		auto it = ls.end();
		it--;
		int a = *it;
		ls.erase(it);
		it = ls.upper_bound(L-a);
		if(it==ls.begin()){
			if(lef!=-1) return -1;
			lef = a;
			continue;
		}
		it--;
		ls.erase(it);
	}
	if(ls.size()==1) lef = *ls.begin();
	return lef + 1;
}
bool can(int L){
	int r = -1;
	rep(i,N) if(G[i].size()==1) r = i;
	int tmp = dfs(r,-1,L);
	if(tmp==-1) return 0;
	if(tmp-1>L) return 0;
	return 1;
}
int main(){
	cin>>N;
	G.resize(N);
	rep(i,N-1){
		int x,y;
		cin>>x>>y;
		x--,y--;
		G[x].pb(y);
		G[y].pb(x);
	}
	int A=0;
	rep(v,N){
		int deg = G[v].size();
		A += deg%2;
	}
	A/=2;
	int ub = N-1, lb = 0;
	while(ub-lb>1){
		int m = (ub+lb)/2;
		if(can(m)) ub = m;
		else lb = m;
	}
	int B = ub;
	cout<<A<<" "<<B<<endl;
}