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:
#pragma comment(linker, "/STACK:102400000,102400000")
#include <fstream>
#include <iostream>
#include <functional>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <ctime>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <cassert>

//#include <unordered_map>
//#include <unordered_set>
using namespace std;

typedef long long ll;
#define eps 1e-8
#define LL_INF 0x3fffffffffffffff
#define INF 1LL<<30
#define mem(a, b) memset(a, b, sizeof(a))
#define pper(i,n,m) for(int i = n;i >= m; i--)
#define repp(i, n, m) for (int i = n; i <= m; i++)
#define rep(i, n, m) for (int i = n; i < m; i++)
#define sa(n) scanf("%d", &(n))
#define slla(n) scanf("%lld", &(n))
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define DE(val) cout<<#val<<": "<<val<<endl;

const int dx4[5] = { 0,-1,0,1,0 };
const int dy4[5] = { 0,0,1,0,-1 };

const int dx8[9] = { 0,-1,0,1,0,1,1,-1,-1 };
const int dy8[9] = { 0,0,1,0,-1,1,-1,1,-1 };
const int maxn = 2e5 + 50;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
ll po(ll a, ll b, ll mod) { ll res = 1; a %= mod; for (; b; b >>= 1) { if (b & 1)res = res*a%mod; a = a*a%mod; }return res; }
ll gcd(ll a, ll b) { if (a == 0) { return b; } else { return gcd(b%a, a); } }
void YES() { puts("YES"); exit(0); }
void Yes() { puts("Yes"); exit(0); }
void NO() { puts("NO"); exit(0); }
void No() { puts("No"); exit(0); }
void one() { puts("-1"); exit(0); }

int n;
vector<int>edge[maxn];
int dp[maxn];

bool dfs(int x, int fa, int up)
{
	vector<int>son;
	if (edge[x].size() & 1)son.push_back(0);
	for (int i = 0; i<edge[x].size(); i++)
	{
		int to = edge[x][i];
		if (to == fa)continue;
		if (!dfs(to, x, up))return false;
		if(dp[to] != -1)son.push_back(dp[to] + 1);
	}

	sort(son.begin(), son.end());

	if (son.size() % 2 == 0)
	{
		int st = 0;
		int en = son.size() - 1;
		while (st < en)
		{
			if (son[st] + son[en] > up)
			{
				return false;
			}
			st++;
			en--;
		}
		dp[x] = -1;
	}
	else
	{
		int le = 0;
		int ri = son.size() - 1;
		int flag = 1;
		while (le < ri)
		{
			int mid = (le + ri) / 2;

			int i = 0;
			int j = son.size() - 1;
			flag = 1;
			while (i < j)
			{
				if (i == mid)i++;
				if (j == mid)j--;
				if (i<j)
				{
					if (son[i] + son[j] > up)
					{
						flag = 0;
						break;
					}
					else
					{
						i++;
						j--;
					}
				}
			}
			if (flag)
			{
				ri = mid;
			}
			else
			{
				le = mid + 1;
			}
		}
		if (son[le] > up)return false;
		int i = 0;
		int j = son.size() - 1;
		while (i < j)
		{
			if (i == le)i++;
			if (j == le)j--;
			if (i<j)
			{
				if (son[i] + son[j] > up)
				{
					return false;
				}
				else
				{
					i++;
					j--;
				}
			}
		}
		dp[x] = son[le];
	}
	return true;
}

void solve()
{
	sa(n);
	repp(i, 1, n - 1)
	{
		int x, y;
		sa(x), sa(y);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	int cnt = 0;
	int p = 1;
	repp(i, 1, n)
	{
		if (edge[i].size() & 1)
		{
			cnt++;
		}
		if (edge[i].size() == 1)
		{
			p = i;
		}
	}
	int ans = cnt / 2;
	int le = 1;
	int ri = n;
	while (le < ri)
	{
		int mid = (le + ri) / 2;
		memset(dp, 0, sizeof(dp));
		if (dfs(p, -1, mid))
		{
			ri = mid;
		}
		else
		{
			le = mid + 1;
		}
	}
	cout << ans << " " << le << endl;
}
int main()
{

	solve();
	// system("pause");
	return 0;
}