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 <vector>
#include <algorithm>
using namespace std;
int N;
vector <int> G[100005];
pair <long long, long long> DP[2][100005];
long long DP2[100005];
int aux;
bool ok;
int a = 0;
void Read()
{
    cin >> N;
    for(int i = 1; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i = 1; i <= N; i++)
        if(G[i].size() % 2 == 1)
            a++;
}
inline bool cmp(int a, int b)
{
    return DP2[a] < DP2[b];
}
bool check2(int pos, int node)
{
    int left = 0, right=  G[node].size() - 1;
    while(left < right)
    {
        if(left == pos)
        {
            left++;
            continue;
        }
        if(right == pos)
        {
            right--;
            continue;
        }
        if(DP2[G[node][left]] + DP2[G[node][right]] > aux)
            return 0;
        left++;
        right--;
    }
    int add = 0;
    if(node == 1)
        add = 1;
    if(DP2[G[node][pos]] + 1 > aux + add)
        return 0;
    return 1;
}
int binS(int node)
{
    int mid, left = 0, right = G[node].size() - 1, sol = -1;
    while(left <= right)
    {
        mid = (left + right) / 2;
        if(check2(mid, node))
        {
            sol = mid;
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    return sol;
}
void DFS(int node, int father)
{
    if(ok == 0)
        return;
    int cnt = 0;
    for(int i = 0; i < G[node].size(); i++)
    {
        int neighb = G[node][i];
        if(neighb == father || neighb == 0)
            continue;
        DFS(neighb, node);
        ++cnt;
    }

    for(auto it = G[node].begin(); it != G[node].end(); it = next(it))
    {
        if(*it == father)
        {
            G[node].erase(it);
            break;
        }

    }
    if(node != 1)
    {
        if(G[node].size() % 2 == 0)
        G[node].push_back(0);
    if(cnt == 0)
    {
        DP2[node] = 1;
        return;
    }
    sort(G[node].begin(), G[node].end(), cmp);
    int p = binS(node);
    if(p == -1)
    {
        ok = 0;
        return;
    }
    DP2[node] = DP2[G[node][p]] + 1;
    }
    else
    {
        sort(G[node].begin(), G[node].end(), cmp);
        if(G[node].size() % 2 == 1)
        {
            int p = binS(node);
            if(p == -1)
            {
                ok = 0;
                return;
            }
        }
        else
        {
            int left = 0, right=  G[node].size() - 1;
            while(left < right)
            {

                if(DP2[G[node][left]] + DP2[G[node][right]] > aux)
                {
                    ok = 0;
                    break;
                }
                left++;
                right--;
            }
        }
    }

}
bool check(int B)
{
    aux = B;ok = 1;
    DFS(1, -1);
    return ok;
}
void binS2()
{
    int left = 1, right = N, mid, sol = N;
    while(left <= right)
    {
        mid = (left+ right) / 2;
        if(check(mid))
        {
            sol = mid;
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    cout << a / 2 << " " << sol << "\n";
}
int main()
{
    Read();
    binS2();
    return 0;
}