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:
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//11:48

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

int DP[N][2], n, x;
pii dp[N];
vi G[N];

void DFS(int v, int p = 0){
	if (G[v].size() == 1 & v != 1){
		DP[v][0] = 1;
		DP[v][1] = 0;
		return;
	}
	int res = 0;
	int ted = 0;
	for (auto u:G[v]){
		if (u == p) continue;
		ted++;
		DFS(u, v);
		res += min(DP[u][0], DP[u][1]);
	}
	DP[v][0] = res + (ted / 2 + (ted % 2));
	ted--;
//	cout << res << ' ' << ted << '\n';
	
	DP[v][1] = res + (ted / 2 + (ted % 2));
//	cout << v << ' ' << DP[v][0] << ' ' << DP[v][1] << '\n';
}

int Best(vi A){
	int pnt = A.size() - 1;
	int res = 0;
	for (int i = 0; i < A.size() / 2; i++){
		if (pnt <= i) break;
		while (pnt > i && A[pnt] + A[i] > x) pnt--;
		if (pnt == i) break;
		res++;
	}
	return res;
}

void DFS2(int v, int p = 0){
	if (G[v].size() == 1 && v != 1){
		dp[v] = {0, 0};
		return;
	}
	int sm = 0;
	vi num;
	for (auto u:G[v]){
		if (u == p) continue;
		DFS2(u, v);
		sm += dp[u].F;
		if (dp[u].S + 1 == x)sm++;
		else num.pb(dp[u].S + 1);
	}
	if (SZ(num) == 0){
		dp[v] = {sm, 0};
		return;
	}
	sort(all(num));
	int B = Best(num);
	dp[v] = {B + SZ(num) - 2 * B + sm, 0};
//	cout << v << ' ' << B << endl;
	vi GG;
	for (int i = 0; i < (int)num.size() - 1; i++){
		GG.pb(num[i]);
	}
	B = Best(GG);
	if (dp[v].F == sm + B + SZ(num) - 2 * B - 1){	
//		cout << v << ' ' << dp[v].F << ' ' << dp[v].S << '\n';
		return;
	}
	int l = -1, r = SZ(num) - 1;
	dp[v].F = sm + B + SZ(num) - 2 * B - 1;
	while (r - l > 1){
		int md = (l + r) >> 1;
		GG.clear();
		for (int i = 0; i < SZ(num); i++){
			if (i != md) GG.pb(num[i]);
		}
		int xx = Best(GG);
		if (dp[v].F == xx + sm + SZ(num) - 2 * B - 1) r = md;
		else l = md;
	}
	dp[v].S = num[r];
	if (dp[v].S == x) dp[v] = {dp[v].F + 1, 0};	
//	cout << v << ' ' << dp[v].F << ' ' << dp[v].S << '\n';
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++){
		int v, u;
		cin >> v >> u;
		G[v].pb(u), G[u].pb(v);
	}
	memset(DP, 31, sizeof DP);
	DFS(1);
	cout << DP[1][0] << ' ';
	int l = 0, r = n;
	while (r - l > 1){
		x = (l + r) >> 1;
		DFS2(1);
		if ((dp[1].F + (dp[1].S != 0) <= DP[1][0])) r = x;
		else l = x;
	}
//	x = 3;
//	DFS2(1);
	cout << r;







	return 0;
}