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>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
    if(c == '-') f = -1;
    c = getchar();
    }
    while(c >= '0' && c <= '9') {
    res = res * 10 + c - '0';
    c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
    out(x / 10);
    }
    putchar('0' + x % 10);
}
int N;
struct node {
    int to,next;
}E[MAXN * 2];
int head[MAXN],sumE;
int dp[MAXN],A,lim,res;
int val[MAXN],tot;
bool vis[MAXN];
void add(int u,int v) {
    E[++sumE].to = v;
    E[sumE].next = head[u];
    head[u] = sumE;
}
void Init() {
    read(N);
    int a,b;
    for(int i = 1 ; i < N ; ++i) {read(a);read(b);add(a,b);add(b,a);}
    
}
void dfs(int u,int fa) {
    int son = 0;
    for(int i = head[u] ; i ; i = E[i].next) {
	int v = E[i].to;
	if(v != fa) {
	    dfs(v,u);
	    ++son;
	    dp[u] += dp[v];
	}
    }
    dp[u] -= son / 2;
    if(son % 2 == 0 && fa) dp[u]++;
}
struct BIT {
    int tr[MAXN],s;
    void clear() {
	for(int i = 1 ; i <= s ; ++i) tr[i] = 0;
    }
    int lowbit(int x) {return x & -x;}
    int query(int x) {
	int res = 0;
	while(x > 0) {
	    res += tr[x];
	    x -= lowbit(x);
	}
	return res;
    }
    void insert(int x,int v) {
	while(x <= s) {
	    tr[x] += v;
	    x += lowbit(x);
	}
    }
    int find_max() {
	int L = 1,R = s;
	int x = query(s);
	if(x == 0) return 0;
	while(L < R) {
	    int m = (L + R + 1) >> 1;
	    if(query(m - 1) != x) L = m;
	    else R = m - 1;
	}
	return L;
    }
}BST;
void calc(int u,int fa) {
    for(int i = head[u] ; i ; i = E[i].next) {
	int v = E[i].to;
	if(v != fa) {
	    calc(v,u);
	}
    }
    tot = 0;
    for(int i = head[u] ; i ; i = E[i].next) {
	int v = E[i].to;
	if(v != fa) {
	    val[++tot] = dp[v];
	}
    }
    if(!tot) {dp[u] = 1;++res;return;}
    BST.clear();
    sort(val + 1,val + tot + 1);
    for(int i = 1 ; i <= tot ; ++i) vis[i] = 1;
    BST.s = tot;int p = 0;
    for(int i = tot ; i >= 1 ; --i) {
	if(!vis[i]) continue;
	while(p < i && val[p + 1] + val[i] <= lim) {
	    ++p;BST.insert(p,1);
	}
	if(p >= i) BST.insert(i,-1);
	int t = BST.find_max();
	if(t) {vis[t] = 0;vis[i] = 0;BST.insert(t,-1);--res;}
    }
    if(fa) {
	dp[u] = 1;++res;
	for(int i = 1 ; i <= tot ; ++i) {
	    if(vis[i]) {
		if(val[i] + 1 > lim) break;
		dp[u] += val[i];--res;
		break;
	    }
	}
    }
}
bool check(int m) {
    lim = m;res = 0;
    calc(1,0);
    return res <= A;
}
void Solve() {
    dfs(1,0);
    out(dp[1]);space;
    A = dp[1];
    int L = 1,R = N - 1;
    while(L < R) {
	int mid = (L + R) >> 1;
	if(check(mid)) R = mid;
	else L = mid + 1;
    }
    out(R);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Init();
    Solve();
}