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<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second

vector<int> G[1 << 17];

int cnt = 0;
void calcnum(int root, int from) {
	int tmp = 0;
	rep(j, G[root].size()) {
		int to = G[root][j];
		if (to == from)continue;
		calcnum(to, root); tmp++;
	}
	cnt += tmp / 2;
	if (root == 0 && tmp % 2)cnt++;
}
int c;
int dfs(int root, int from) {
	vector<int> v;
	rep(j, G[root].size()) {
		int to = G[root][j];
		if (to == from)continue;
		int cto = dfs(to, root);
		if (cto == c) {
			cnt++;
		}
		else {
			v.push_back(cto);
		}
	}
	sort(v.begin(), v.end());
	int len = v.size();
	multiset<int> mt;
	rep(i, len)mt.insert(v[i]);
	vector<int> rest;
	while(len) {
		cnt++;
		auto itr = mt.end(); itr--;
		int z = *itr; mt.erase(mt.find(z)); len--;
		int r = c - z;
		if (mt.count(r)) {
			mt.erase(mt.find(r)); len--;
		}
		else {
			mt.insert(r);
			auto itr2 = mt.find(r);
			if (itr2 == mt.begin()) {
				mt.erase(itr2);
				rest.push_back(z);
				continue;
			}
			itr2--; mt.erase(r);
			mt.erase(itr2); len--;
		}
	}
	if (rest.size()) {
		cnt--;
		return rest[rest.size() - 1] + 1;
	}
	else return 1;
}
int ansa;
bool test(int x) {
	c = x; cnt = 0;
	int u = dfs(0, -1) - 1; if (u > 0)cnt++;
	return cnt == ansa;
}
void solve() {
	int n; cin >> n;
	rep(i, n - 1) {
		int a, b; cin >> a >> b; a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	calcnum(0, -1);
	ansa = cnt;
	int le = 0, ri = n;
	while (ri - le > 1) {
		int mid = (ri + le) / 2;
		if (test(mid)) {
			ri = mid;
		}
		else {
			le = mid;
		}
	}
	cout << ansa << " " << ri << endl;
}
int main() {
	solve();
	//stop
	return 0;
}