p03484 AtCoder Regular Contest 088 - Christmas Tree
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
```python
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from bisect import bisect_left, bisect_right

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

def make_pairs(S,x):
    # a + b <= x となるペアをなるべくたくさん作る
    # nペア（なるべくたくさん）作ったあと、1つ短い長さが残る
    seg = 0
    while S and S[-1] == x:
        S.pop()
        seg += 1
    i = bisect_right(S,x//2)
    lower = S[:i][::-1]; upper = S[i:]
    cand = []
    rest = []
    for b in upper[::-1]:
        while lower and lower[-1] + b <= x:
            cand.append(lower.pop())
        if cand:
            cand.pop()
            seg += 1
        else:
            rest.append(b)
    cand += lower[::-1]
    L = len(cand)
    q,r = divmod(L,2)
    if r:
        return seg + len(rest) + q, cand[0]
    else:
        seg += q
        if rest:
            return seg + len(rest) - 1, rest[-1]
        else:
            # 全部ペアになった
            return seg, 0

def solve(x):
    # 長さ x までの線分を許容した場合に、必要となる本数を返す
    dp = [0] * (N+1)
    temp = [[] for _ in range(N+1)] # 下から出てくる長さ
    for v in order[::-1]:
        p = parent[v]
        S = temp[v]
        S.sort()
        s, l = make_pairs(S,x)
        dp[v] += s        
        dp[p] += dp[v]
        temp[p].append(l + 1)
        if v == 1:
            return dp[1] if not l else dp[1] + 1

seg = solve(N + 10)
left = 0 # むり
right = N # できる
while left + 1 < right:
    x = (left + right) // 2
    if solve(x) == seg:
        right = x
    else:
        left = x
print(seg, right)
```