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:
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
#define vv(a,b,c,d) vector<vector<a> >(b,vector<a>(c,d))
#define vvv(a,b,c,d,e) vector<vector<vector<a> > >(b,vv(a,c,d,e))
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

const int INF = 100005;
int N;
vi G[100005];
vi va[100005];

int bin(vi &a, int r, int lim) {
    auto g = [&](int mid) {
        int i = 0, j = r - 1;
        for (int k = 0; k < r / 2;) {
            if (i == mid) i++;
            else if (j == mid)j--;
            else {
                k++;
                if (a[i++] + a[j--] > lim) {
                    RT 0;
                }
            }
        }
        RT 1;
    };

    if (!g(r - 1))RT - 1;

    int ok = r - 1, ng = -1;
    while (ok - ng > 1) {
        int mid = (ok + ng) / 2;
        (g(mid) ? ok : ng) = mid;
    }

    RT ok;
}

int f(int u, int p, int lim) {
    int C = sz(G[u]) - 1;

    auto &a = va[u];
    if (sz(a) < C) {
        a.reserve(C);
        a.resize(C);
    }

    for (int i = 0, j = 0; i < sz(G[u]); ++i) {
        int v = G[u][i];
        if (v != p) {
            a[j++] = f(v, u, lim);
        }
    }
    sort(all(a));
    if (sz(a) && a.back() > lim)RT INF;

    if (C % 2) {
        int k = bin(a, C, lim);
        if (k == -1)RT INF;
        RT a[k] + 1;
    } else {
        int chk = 1;
        rep(i, C / 2) {
            if (a[i] + a[C - 1 - i] > lim) {
                chk = 0;
                break;
            }
        }
        if (chk)RT 1;

        int k = bin(a, C - 1, lim);
        if (k == -1 || u == 1)RT INF;

        RT a[k] + 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    cin >> N;
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int A = 0;
    rep(i, N + 1)A += sz(G[i]) & 1;
    A /= 2;
    G[1].push_back(0);

    int ng = 0, ok = N;
    while (ok - ng > 1) {
        int mid = (ng + ok) / 2;
        int re = f(1, 0, mid);
        (re - 1 <= mid ? ok : ng) = mid;
    }
    
    int B = ok;
    cout << A << ' ' << B << endl;
}