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:

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all(C) std::begin(C), std::end(C)

int32_t N;
std::vector<int32_t> edge[101000];

int32_t F(std::vector<int32_t>& a, int32_t K)
{
	std::sort(a.begin(),a.end());
	int lb = -1, ub = a.size();
	while (ub - lb>1) {
		int mid = (ub + lb) / 2;

		bool f = true;
		int l = 0, r = a.size() - 1;
		for (int i = 0; i < a.size() / 2;++i) {
			if (l == mid)l++;
			if (r == mid)r--;
			if (a[l] + a[r]>K)f = false;
			l++; r--;
		}
		if (f)ub = mid;
		else lb = mid;
	}
	return ub;
}

volatile bool func_ok = false;
int32_t len_max;
int32_t func(int32_t v, int32_t parent)
{
	//if (edge[v].size() == 1) {
	//	return 0;
	//}
	//if (edge[v].size() == 2) {
	//	for (auto& e : edge[v]) {
	//		if (e != parent) { return 1 + func(e, v); }
	//	}
	//}

	std::multiset<int32_t, std::greater<int32_t>> L;
	for (auto& e : edge[v]) {
		if (e != parent) {
			L.insert(1 + func(e, v));
		}
	}
	if (L.size() % 2 == 0) {
		L.insert(0);
	}

	std::vector<int32_t> T;
	for (auto& i : L) { T.push_back(i); }
	auto R = F(T, len_max);
	if(R==T.size()){
		func_ok = false;
		return 0;
	}
	else {
		return T[R];
	}

	while (L.size()>=2) {
		auto iter2 = L.begin();
		auto iter1 = L.lower_bound(len_max - *iter2);
		if (iter1 == L.end()) {
			func_ok = false;
			return 0;
		}
		if (iter1 == iter2) {
			++iter1;
		}
		L.erase(iter1);
		L.erase(iter2);
	}
	return *L.begin();
}
bool func_2(int32_t v)
{
	func_ok = true;
	auto res = (func(edge[v][0], v) + 1 <= len_max);
	return func_ok&&res;
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);
	if(0){

		len_max = 10;
		std::multiset<int32_t, std::greater<int32_t>> L;
		L.insert(9);
		L.insert(8);
		L.insert(4);

		if (L.size() % 2 == 0) {
			L.insert(0);
		}

		while (L.size() >= 2) {
			auto iter2 = L.begin();
			auto iter1 = L.upper_bound(len_max - *iter2);
			if (iter1 == L.end()) {
				func_ok = false;
				//return 0;
				break;
			}
			if (iter1 == iter2) {
				++iter1;
			}
			L.erase(iter1);
			L.erase(iter2);
		}
	}
	in >> N;
	for (int32_t i = 0; i < N-1; i++)
	{
		int a, b;
		in >> a >> b; --a; --b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	int32_t A = 1;
	for (int32_t i = 0; i < N; i++)
	{
		A += (edge[i].size() - 1) / 2;
	}
	out << A << ' ';

	int32_t root = 0;
	for (int32_t i = 0; i < N; i++)
	{
		if (edge[i].size() == 1) {
			root = i; break;
		}
	}

	using BS_INT = int64_t;
	BS_INT ok_range = N, ng_range = 0;
	while (std::abs(ok_range - ng_range) > 1) {
		BS_INT mid = (ok_range + ng_range) / 2;
		bool is_ok = false;

		//ここに書く
		len_max=mid;
		is_ok = func_2(root);

		if (is_ok) {
			ok_range = mid;
		}
		else {
			ng_range = mid;
		}
	}
	out << ok_range << endl;


	return 0;
}
#endif