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 <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 18;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

vector <int> conn[100050];
vector <int> son[100050];
bool dchk[100050];
void DFS1(int n) {
	dchk[n] = true;
	for (auto it : conn[n]) {
		if (dchk[it]) continue;
		son[n].push_back(it);
		DFS1(it);
	}
}

int N;
int tus;
int dp[100050][2];
vector <int> Vu[100050];
void DFS2(int n) {
	dp[n][0] = 0;
	dp[n][1] = 0;
	Vu[n].clear();
	for (auto it : son[n]) {
		DFS2(it);
		dp[n][0] += dp[it][0];
		if (dp[it][1] >= tus) {
			dp[n][0]++;
			Vu[n].push_back(1);
		}
		else Vu[n].push_back(dp[it][1]);
	}
	sort(all(Vu[n]));

	int st = 1, en = Vu[n].size() / 2, mi, rv = 0, i;
	while (st <= en) {
		mi = (st + en) / 2;
		for (i = 0; i < mi; i++) if (Vu[n][i] + Vu[n][2 * mi - 1 - i] + 1 > tus) break;
		if (i >= mi) {
			rv = mi;
			st = mi + 1;
		}
		else en = mi - 1;
	}
	dp[n][0] += Vu[n].size() - rv;
	if (rv * 2 == Vu[n].size()) {
		dp[n][1] = 1;
		return;
	}

	dp[n][0]--;
	int st2 = 0, en2 = 2 * rv - 1, mi2, rv2 = 2 * rv;
	while (st2 <= en2) {
		mi2 = (st2 + en2) / 2;
		for (i = 0; i < rv; i++) {
			int t1 = i, t2 = 2 * rv - i - 1;
			if (t1 >= mi2) t1++;
			if (t2 >= mi2) t2++;
			if (Vu[n][t1] + Vu[n][t2] + 1 > tus) break;
		}
		if (i >= rv) {
			rv2 = mi2;
			en2 = mi2 - 1;
		}
		else st2 = mi2 + 1;
	}
	dp[n][1] = 1 + Vu[n][rv2];
}
int getv(int x) {
	tus = x;
	DFS2(1);
	return dp[1][0] + !!(dp[1][1] - 1);
}
int main() {
	int i;
	scanf("%d", &N);
	for (i = 1; i < N; i++) {
		int t1, t2;
		scanf("%d %d", &t1, &t2);
		conn[t1].push_back(t2);
		conn[t2].push_back(t1);
	}
	DFS1(1);

	int st = 2, en = N-1, mi, rv = N;
	while (st <= en) {
		mi = (st + en) / 2;
		if (getv(mi) == getv(rv)) {
			rv = mi;
			en = mi - 1;
		}
		else st = mi + 1;
	}
	printf("%d %d\n", getv(rv), rv - 1);
	return 0;
}