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 <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=100000;

int n;
vector<int> adj[MAXN];

int cnt[MAXN];
int parlen[MAXN];
int mxlen[MAXN];
int limit;

int cur[MAXN],ncur;

bool dfs(int at,int par) {
	//printf("dfs(%d,%d)\n",at+1,par+1);
	REPSZ(i,adj[at]) {
		int to=adj[at][i]; if(to==par) continue;
		if(!dfs(to,at)) return false;
	}
	cnt[at]=1,mxlen[at]=0; ncur=0;
	REPSZ(i,adj[at]) {
		int to=adj[at][i]; if(to==par) continue;
		cnt[at]+=cnt[to];
		mxlen[at]=max(mxlen[at],mxlen[to]);
		cur[ncur++]=parlen[to];
	}
	sort(cur,cur+ncur);
	int pos=0,nskipped=0,mnskipped=-1,res=-1,single=-1;
	for(int i=ncur-1;i>=0;--i) {
		if(pos>=i) {
			if(pos==i) {
				if(mnskipped==-1) mnskipped=cur[pos];
				++nskipped;
			}
			break;
		}
		if(cur[pos]+cur[i]>limit) {
			if(nskipped>0) { --nskipped; if(nskipped==0) mnskipped=-1; continue; }
			if(ncur%2==0&&single==-1) { mxlen[at]=max(mxlen[at],cur[i]); single=cur[i]; continue; }
			if(res==-1) { res=cur[i]+1; continue; }
			return false;
		}
		while(pos+1<i&&cur[pos+1]+cur[i]<=limit) {
			if(mnskipped==-1) mnskipped=cur[pos];
			++nskipped,++pos;
		}
		mxlen[at]=max(mxlen[at],cur[pos]+cur[i]);
		++pos;
	}
	nskipped%=2;
	if(nskipped==0&&res==-1) res=1;
	if(nskipped==1&&res==-1) res=mnskipped+1;
	parlen[at]=res; mxlen[at]=max(mxlen[at],parlen[at]); cnt[at]-=(ncur+1)/2;
	//printf("limit=%d: %d -> cnt=%d parlen=%d mxlen=%d\n",limit,at+1,cnt[at],parlen[at],mxlen[at]);
	//printf("cur:"); REP(i,ncur) printf(" %d",cur[i]); puts("");
	return mxlen[at]<=limit;		
}

void run() {
	scanf("%d",&n);
	REP(i,n-1) { int a,b; scanf("%d%d",&a,&b); --a,--b; adj[a].PB(b); adj[b].PB(a); }
	//n=MAXN; REP(i,n-1) adj[0].PB(i+1),adj[i+1].PB(0);

	int rt=0; while(SZ(adj[rt])!=1) ++rt; //printf("rt=%d\n",rt+1);
	int x=adj[rt][0];
	limit=INT_MAX;
	assert(dfs(x,rt));
	int rescnt=cnt[x];
	int l=0,r=mxlen[x];
	while(l+1<r) {
		limit=l+(r-l)/2;
		if(dfs(x,rt)) r=limit; else l=limit;
	}
	printf("%d %d\n",rescnt,r);
}

int main() {
	run();
	return 0;
}