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 YES "YES"
#define NO "NO"
#define YESNO OUT(three(solve(),YES,NO))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(a);i>=(LL)(b);i--)
#define REP(i,b) FOR(i,zero,b)
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,zero,b)
#define ALL(c) c.begin(),c.end()
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define int LL
#define zero 0LL
using namespace std;
template<typename T> inline void maximize(T &a,T b){a=max(a,b);}
template<typename T> inline void minimize(T &a,T b){a=min(a,b);}
template<typename T> inline bool middle(T a,T b,T c){return b<=a && a<=c;}
typedef long long LL;
typedef double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut,ut> pr;
typedef pair<ut,pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr,Vpr,greater<pr> > PQ;
inline void outputVI(VI x){REP(i,SI(x)){cout << three(i," ","") << x[i];}OUT("");}
const int SIZE1=1e6+1000;
const int SIZE2=2020;
const int SIZE3=410;
const int SIZE=SIZE1;
const LL p=7+1e9;
const LL INF=1LL<<60;
const long double EPS=1e-7;
string S;
ut N,M,K,X,Y;
// ut A,B,C,D,E,F,G,H,I,J,L,O,P,Q,R,T,U;
VI edges[SIZE];
LL vals[SIZE],nums[SIZE],maps[SIZE2][SIZE2],answer=zero;
 
////////////////////////////////////////////////////////////////////////////////////////////
 
////////////////////////////////////////////////////////////////////////////////////////////
VI points[SIZE];
bool reached[SIZE];
int used[SIZE];
bool able2(int x,int t){
	int s=0,e=points[x].size()-1;
	while(s<=e){
		if(s==t){
			s++;
		}else if(e==t){
			e--;
		}else{
			if(points[x][s]+points[x][e]>X) return false;
			s++;
			e--;
		}
	}
	return true;
}
int pack(int x){
	int s=0,e=points[x].size()-1;
	while(s<=e){
		int f=(s+e)/2;
		if(able2(x,f)) e=f-1;
		else s=f+1;
	}
	if(s==SI(points[x])) return -1;
	return points[x][s];
}
bool able(int x){
	X=x;
	queue<int> qu;
	REP(now,N+1) reached[now]=used[now]=0;
	REP(now,N+1) points[now].clear();
	EFOR(i,1,N){
		points[i].clear();
		if(SI(edges[i])==1) {
			qu.push(i);
		}
	}

	while(!qu.empty()){
		int now=qu.front();
		reached[now]=true;
	
		qu.pop();
	//	outputVI(points[now]);
	//	DEBUG(now);
		if(used[now]==SI(edges[now])){
			points[now].PB(0);
			if(SI(points[now])%2==0) points[now].PB(0);
			sort(ALL(points[now]));
			return able2(now,0);
		}
		if(SI(points[now])%2==0) points[now].PB(0);
		sort(ALL(points[now]));
		int nokori=pack(now);
		if(nokori==-1) return false;
		REP(i,edges[now].size()){
			int next=edges[now][i];
			used[next]++;
			if(!reached[next] && used[next]>=SI(edges[next])-1){
				qu.push(next);
				points[next].PB(nokori+1);
			}else if(!reached[next]){
				points[next].PB(nokori+1);	
			}
		}
	}
	return true;
}
LL solve(){
	cin >> N;
	int a,b;
	REP(i,N-1){
		cin >>a >> b;
		edges[a].PB(b);
		edges[b].PB(a);
	}
	int A=1;
	EFOR(i,1,N){
		A+=(SI(edges[i])-1)/2;
	}
	int s=0,e=N-1;
	while(s<=e){
		int f=(s+e)/2;
	//	DEBUG(f);
		if(able(f)) e=f-1;
		else s=f+1;
	}
	cout << A <<" " << s << endl;
	return 0;
}
signed main(){
//	OUT(solve());
	solve();
	return 0;
}