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 <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

const int L=1e5+10;
vector<int> es[L];
int m;
int f(int r,int p) {
	vector<int> len;
	for(int i:es[r]){
		if(i==p)continue;
		int v=f(i,r);
		if(v>m){
			return m+1;
		}
		len.push_back(v);
	}
	if(len.size()%2==0){
		len.push_back(0);
	}
	sort(len.begin(),len.end());
	int low=-1;
	int hi=len.size();
	while(low+1<hi){
		int c=(low+hi)/2;
		int h=0;
		int t=len.size()-1;
		if(h==c)h++;
		if(t==c)t--;
		bool ok=true;
		while(h<t){
			if(len[h]+len[t]>m){
				ok=false;
				break;
			}
			h++;
			t--;
			if(h==c)h++;
			if(t==c)t--;
		}
		if(ok){
			hi=c;
		}
		else{
			low=c;
		}
	}
	if(hi<len.size()){
		//cerr << m << ", " << r << ", " << p << ", " << len[hi]+1 << endl;
		return len[hi]+1;
	}
	return m+1;
}
int main() {
	int N;
	cin >> N;
	for(int i=0;i<N-1;i++){
		int a,b;
		cin >> a >> b;
		es[a].push_back(b);
		es[b].push_back(a);
	}
	int c=0;
	int s=0;
	for(int i=1;i<=N;i++){
		c+=es[i].size()%2;
		if(es[i].size()==1){
			s=i;
		}
	}

	int low=0,hi=N-1;
	while(low+1<hi){
		m=(low+hi)/2;
		//cerr << low << ", " << hi << ", " << m << ": " << f(s,0) << endl;
		if(f(es[s][0],s)<=m){
			hi=m;
		}
		else{
			low=m;
		}
	}
	cout << c/2 << " " << hi << endl;

	return 0;
}