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>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cerr << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

const int maxn = 100010;
const int INF = TEN(9);

V<int> g[maxn];
int r;

int dfs(int v, int p, int l) {
	V<int> vec;
	for (int to : g[v]) if (to != p) {
		int res = dfs(to, v, l);
		if (res == -1 || res > l) {
			return -1;
		}
		vec.pb(res);
	}
	sort(ALL(vec));
	int sz = vec.size();

	if (sz % 2 == 0) {
		{
			//all
			int nl = 0, nr = sz - 1;
			bool f = 1;
			rep(i, sz / 2) {
				if (vec[nl] + vec[nr] > l) {
					f = 0;
				}
				++nl; --nr;
			}
			if (f) {
				return 1;
			}
		}
		vec.pop_back();
		--sz;		
	}

	//sz : odd

	auto valid = [&](int p) {
		int nl = 0, nr = sz - 1;
		bool f = 1;

		rep(i, sz / 2) {
			if (nl == p) ++nl;
			if (nr == p) --nr;
			if (vec[nl] + vec[nr] > l) {
				f = 0;
			}
			++nl; --nr;
		}
		return f;
	};

	int lo = 0, hi = sz - 1;
	if (valid(lo)) {
		hi = 0;
	}
	if (!valid(hi)) {
		return -1;
	}

	while (hi - lo > 1) {
		int m = (lo + hi) / 2;
		if (valid(m)) hi = m;
		else lo = m;
	}
	return vec[hi] + 1;
}

bool ok(int l) {
	int res = dfs(r, -1, l);
	return (res != -1);
}

int main() {
	int N; cin >> N;
	rep(i, N-1) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		g[a].pb(b); g[b].pb(a);
	}

	rep(i, N) if (g[i].size() == 1) {
		r = i;
		break;
	}

	int A = 0;
	rep(i, N) if (g[i].size() % 2 == 1) ++A;

	int lo = 0, hi = N;
	while (hi - lo > 1) {
		int m = (lo + hi) / 2;
		if (ok(m)) {
			hi = m;
		} else {
			lo = m;
		}
	}

	printf("%d %d\n", A / 2, hi);
	return 0;
}