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 For(i,l,r) for(int i = (l),i##end = (r);i <= i##end;i++)
#define Fordown(i,r,l) for(int i = (r),i##end = (l);i >= i##end;i--)
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef long long ll;

template <typename T> inline bool chkmin(T &x,T y) { return y < x ? x = y,1 : 0; }
template <typename T> inline bool chkmax(T &x,T y) { return x < y ? x = y,1 : 0; }

const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

int to[N << 1],nex[N << 1],beg[N],deg[N],Ans[N],rest[N],A[N];
int e,ans = 0;

inline int read() {
	int x = 0,flag = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')flag = -1,ch = getchar();
	while(isdigit(ch))x = (x << 3) + (x << 1) + (ch - '0'),ch = getchar();
	return x * flag;
}

inline void add(int x,int y) {
	to[++e] = y,nex[e] = beg[x],beg[x] = e;
}

inline void dfs(int x,int fa) {
	int cur = 0;
	for(int i = beg[x];i;i = nex[i]) {
		if(to[i] == fa) continue;
		dfs(to[i],x),cur++;
	}
	ans -= cur / 2,cur &= 1;
	if(!cur && x > 1) ans++;
}

inline int check(int Ban,int top,int val) {
	int pos = top,tot = 0;
	For(i,1,top) {
		if(i == Ban) continue;
		while(pos && (A[i] + A[pos] > val || pos == Ban)) pos--;
		if(i >= pos) break;
		tot++,pos--;
	}
//	debug(tot);
	return tot;
}

inline void Dp(int x,int fa,int val) {
	int total = 0,top = 0;
	for(int i = beg[x];i;i = nex[i]) {
		if(to[i] == fa) continue;
		Dp(to[i],x,val);
	}
	for(int i = beg[x];i;i = nex[i]) {
		if(to[i] == fa) continue;
		total += Ans[to[i]];
		A[++top] = rest[to[i]];
	}
	sort(A + 1,A + top + 1);
//	cout << A[top] << " " << val << endl;
	while(top && A[top] >= val) top--;
	A[top + 1] = 0;
	int pos = top,tot = 0;
//	debug(top);
	For(i,1,top) {
		while(A[i] + A[pos] > val) pos--;
		if(i >= pos) break;
		tot++,pos--;
	}
//	debug(tot);
	int l = 1,r = top + 1;
	while(l < r) {
		int mid = (l + r) >> 1;
//		debug(mid);
		if(check(mid,top,val) < tot) l = mid + 1;
		else r = mid;
	}
//	debug(l);
	rest[x] = A[l] + 1;Ans[x] = total - tot;
	if(l == top + 1 && x > 1) Ans[x]++;
//	cout << x << " " << Ans[x] << " " << total << " " << tot << " " << rest[x] << endl;
}

int main() {
	int n = read();
	For(i,1,n - 1) {
		int x = read(),y = read();
		add(x,y),add(y,x);
	}
	dfs(1,0);
	int l = 1,r = n;
	while(l < r) {
		int mid = (l + r) >> 1;
//		debug(mid);
		Dp(1,0,mid);
//		debug(Ans[1]);
//		cout << "------" << endl;
		if(Ans[1] > ans) l = mid + 1;
		else r = mid;
	}

	printf("%d %d\n",ans,l);

	return 0;
}