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 <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(x,y) (x=min(x,y))
#define chmax(x,y) (x=max(x,y))
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

#define N 100010
vector<int> g[N];
int n, x;
bool ok;
int r = 0;
bool used[N];

int dfs(int u){
	used[u] = true;
	multiset<int> d;
	for(auto v: g[u]){
		if(used[v]) continue;
		int t = dfs(v)+1;
		d.insert(t);
		if(!ok) return INF;
	}
	if(d.size()%2==0) d.insert(0);

	while(d.size()>1){
		auto it = d.end(); --it;
		if(it!=d.begin() && *d.begin()+*it>x) --it;
		int k = *it;
		d.erase(it);
		auto it2 = d.upper_bound(x-k);
		if(it2==d.begin()){
			ok = false;
			break;
		}
		--it2;
		d.erase(it2);
	}
	if(*d.begin()>x) ok = false;
	used[u] = false;
	return *d.begin();
}

int main(){
	cin>>n;
	rep(i, n-1){
		int u, v;
		cin>>u>>v; u--; v--;
		g[u].push_back(v); g[v].push_back(u);
	}
	int resa = 0, resb = 0;
	rep(i, n){
		resa += (g[i].size()-1)/2;
		resb += g[i].size()%2;
		if(g[i].size()==1) r = i;
	}
	resa++; resb /= 2;
	if(resa!=resb) return -1;
	int lb = -1, ub = n;
	while(ub-lb>1){
		x = (lb+ub+1)/2;
		ok = true;
		mset(used, 0);
		dfs(r);
		(ok?ub:lb)=x;
	}
	cout<<resb<<" "<<ub<<endl;
	return 0;
}