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 <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
int n,d[SZ],up[SZ]; Edg
int pr[SZ],seg[SZ];
int qmin(int l,int r)
{
	int ans=1e9; ++l, ++r;
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1)
	{
		if(~l&1) ans=min(ans,seg[l^1]);
		if(r&1) ans=min(ans,seg[r^1]);
	}
	return ans;
}
bool mat(int l1,int r1,int r2)
{
	if(l1>r1) return 1;
	//for i in [l1,r1]
	//pr[i]>=r2+l1-i
	return qmin(l1,r1)>=l1+r2;
}
bool chk(int x,int l,int f=0)
{
	vector<int> ch;
	for esb(x,e,b) if(b!=f)
	{
		bool s=chk(b,l,x);
		if(!s||up[b]>l) return 0;
		ch.pb(up[b]);
	}
	sort(ch.begin(),ch.end());
	int s=ch.size();
	if(s%2==0) //easy
	{
		bool bad=0;
		for(int i=0;i<s/2;++i)
			if(ch[i]+ch[s-1-i]>l) bad=1;
		if(!bad) {up[x]=1; return 1;} --s;
	}
	for(int i=0,j=s-1;i<s;++i)
	{
		while(j>=0&&ch[i]+ch[j]>l) --j;
		pr[i]=j;
	}
	M=1; while(M<=s+3) M<<=1;
	for(int i=0;i<s;++i) seg[i+M+1]=pr[i]+i;
	for(int i=M-1;i>=1;--i)
		seg[i]=min(seg[i+i],seg[i+i+1]);
	up[x]=-1;
	for(int i=0;i<s;++i)
	{
		bool c1=0;
		if(i<s/2)
			c1=mat(0,i-1,s-1)&&mat(i+1,s/2,s-i-1);
		else
			c1=mat(0,s-i-2,s-1)&&mat(s-i-1,s/2-1,i-1);
		if(!c1) continue;
		up[x]=ch[i]+1; break;
	}
	if(up[x]==-1) return 0;
	return 1;
}
int main()
{
	scanf("%d",&n);
	for(int i=1,a,b;i<n;++i)
		scanf("%d%d",&a,&b),adde(a,b),++d[a],++d[b];
	int ans=n,ro=1;
	for(int i=n;i>=1;--i)
		if(d[i]&1) ro=i;
	for(int i=1;i<=n;++i)
		ans-=(d[i]-(i!=ro)+1)/2;
	printf("%d ",ans);
	int l=0,r=n;
	while(l<r)
	{
		int m=(l+r)>>1;
		bool s=chk(ro,m);
		if(s&&up[ro]<=m+1) r=m; else l=m+1;
	}
	printf("%d\n",l);
}