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 REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
using namespace std;

template <typename UnaryPredicate>
int binsearch(int l, int r, UnaryPredicate p) {
    assert (l <= r);
    -- l;
    while (r - l > 1) {
        int m = l + (r - l) / 2;  // avoid overflow
        (p(m) ? r : l) = m;
    }
    return r;
}

int main() {
    // input
    int n; scanf("%d", &n);
    vector<vector<int> > g(n);
    REP (i, n - 1) {
        int a, b; scanf("%d%d", &a, &b);
        -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    // solve
    constexpr int root = 0;
    int a = 0; {
        vector<char> used(n);
        function<void (int, int)> use_chain = [&](int i, int parent) {
            used[i] = true;
            for (int j : g[i]) if (j != parent and not used[j]) {
                use_chain(j, i);
                break;
            }
        };
        function<void (int, int)> go = [&](int i, int parent) {
            int count_not_used = 0;
            for (int j : g[i]) if (j != parent) {
                if (not used[j]) {
                    count_not_used += 1;
                    use_chain(j, i);
                }
                go(j, i);
            }
            a += (count_not_used + 1) / 2;
        };
        go(root, -1);
    }
    int b = binsearch(1, n, [&](int b) {
        int count_chain = 0;
        function<int (int, int)> go = [&](int i, int parent) {
            map<int, int> chain;
            for (int j : g[i]) if (j != parent) {
                int length = go(j, i);
                if (length - 1 >= 1) {
                    chain[length - 1] += 1;
                }
            }
            for (auto it = chain.begin(); it != chain.end(); ) {
                // pop
                int length, count; tie(length, count) = *it;
                chain[length] = 0;
                // make pairs
                while (count) {
                    it = chain.lower_bound(b - length);
                    if (it == chain.end()) break;
                    if (it->first == length) {
                        assert (it->second == 0);
                        count_chain -= count / 2;
                        count %= 2;
                    } else {
                        int delta = min(count, it->second);
                        count_chain -= delta;
                        count -= delta;
                        it->second -= delta;
                    }
                    if (not it->second) {
                        chain.erase(it);
                    }
                }
                // write back
                if (count) {
                    chain[length] = count;
                } else {
                    chain.erase(length);
                }
                // increment
                it = chain.lower_bound(length + 1);
            }
            if (chain.empty()) {
                if (i == root) {
                    return -1;
                } else {
                    count_chain += 1;
                    return b;
                }
            } else {
                return chain.rbegin()->first;
            }
        };
        go(root, -1);
        return count_chain <= a;
    });
    // output
    printf("%d %d\n", a, b);
    return 0;
}