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<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const double PI=acos(-1);
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(a);i>=(b);i--)
#define Rep(i,a,b) for (int i=(a);i<(b);i++)
#define Per(i,a,b) for (int i=(a);i>(b);i--)
#define travel_set(it,a) for (set<int>::iterator (it)=(a).begin();(it)!=(a).end();(it)++)
#define travel_map(it,a) for (map<int>::iterator (it)=(a).begin();(it)!=(a).end();(it)++)
#define travel_vec(it,a) for (vector<int>::iterator (it)=(a).begin();(it)!=(a).end();(it)++)
#define p(x) cout << x << endl;
#define def cout << "find" << endl;
#define what_is(x) cout << #x << " is " << x << endl;
template <class T>T sqr(T x){return x*x;}
template <class T>T alex(T x){return (x>0)?x:-x;}
template <class T>void read(T&x){
	x=0;T f=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if (ch=='-')f=-1,ch=getchar();
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=f;
}

//---------------------------------------------------head---------------------------------------------------

int n;
#define maxn 100005
struct Edge{
	int son[maxn<<1],nxt[maxn<<1],lnk[maxn],tot;
	void add(int x,int y){
		tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
		tot++;son[tot]=x;nxt[tot]=lnk[y];lnk[y]=tot;
	}
}edge;
int cnt[maxn];
int middle;
int f[maxn],g[maxn];
int father[maxn];
bool vis[maxn];
void setfather(int now){
	vis[now]=true;
	for (int j=edge.lnk[now];j;j=edge.nxt[j])
		if (!vis[edge.son[j]]){
			father[edge.son[j]]=now;setfather(edge.son[j]);
		}
}
bool used;
int cwy[maxn];
int d[maxn];
bool check_que(int mid){
	d[0]=0;
	rep(i,1,cwy[0])if (i!=mid)d[++d[0]]=cwy[i];
	rep(i,1,d[0])if (d[i]+d[d[0]-i+1]>middle)return false;
	return true;
}
void dfs(int now){
	for (int j=edge.lnk[now];j;j=edge.nxt[j])if (edge.son[j]!=father[now])
		dfs(edge.son[j]);
	// vector<int>cwy;cwy.clear();
	cwy[0]=0;
	for (int j=edge.lnk[now];j;j=edge.nxt[j])if (edge.son[j]!=father[now]){
		cwy[++cwy[0]]=f[edge.son[j]]+1;
	}
	if (cnt[now])cwy[++cwy[0]]=0;
	sort(cwy+1,cwy+cwy[0]+1);
	if (now==1){
		rep(i,1,cwy[0]/2)if (cwy[i]+cwy[cwy[0]-i+1]>middle)used=false;
	}
	else{
		if (cnt[now]){
			int l=1,r=cwy[0];
			while (l<=r){
				int mid=(l+r)>>1;
				if (check_que(mid))r=mid-1;
				else l=mid+1;
			}
			if (l>cwy[0])used=false;
			else f[now]=cwy[l];
		}
		else{
			int l=1,r=cwy[0];
			while (l<=r){
				int mid=(l+r)>>1;
				if (check_que(mid))r=mid-1;
				else l=mid+1;
			}
			if (l>cwy[0])used=false;
			else f[now]=cwy[l];
		}
	}
	// printf("%d %d %d\n",now,f[now],used);
}
bool check(int mid){
	middle=mid;
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	memset(vis,0,sizeof(vis));
	used=true;dfs(1);return used;
}
int main(){
	read(n);
	Rep(i,1,n){
		int x,y;read(x);read(y);
		edge.add(x,y);
		cnt[x]^=1;cnt[y]^=1;
	}
	int ans=0;
	rep(i,1,n)if (cnt[i])ans++;
	printf("%d ",ans/2);
	int l=1,r=n;setfather(1);
	// printf("%d\n",check(4));
	// printf("%d\n",check(2));
	while (l<=r){
		int mid=(l+r)>>1;
		if (check(mid))r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",l);return 0;
}