You have unweighted tree of n vertices. You have to assign a positive weight to each edge so that the following condition would hold:

  * For every two different leaves v_{1} and v_{2} of this tree, [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of weights of all edges on the simple path between v_{1} and v_{2} has to be equal to 0. 



Note that you can put very large positive integers (like 10^{(10^{10})}).

It's guaranteed that such assignment always exists under given constraints. Now let's define f as the number of distinct weights in assignment.

<image> In this example, assignment is valid, because bitwise XOR of all edge weights between every pair of leaves is 0. f value is 2 here, because there are 2 distinct edge weights(4 and 5).

<image> In this example, assignment is invalid, because bitwise XOR of all edge weights between vertex 1 and vertex 6 (3, 4, 5, 4) is not 0. 

What are the minimum and the maximum possible values of f for the given tree? Find and print both.

Input

The first line contains integer n (3 ≤ n ≤ 10^{5}) — the number of vertices in given tree.

The i-th of the next n-1 lines contains two integers a_{i} and b_{i} (1 ≤ a_{i} < b_{i} ≤ n) — it means there is an edge between a_{i} and b_{i}. It is guaranteed that given graph forms tree of n vertices.

Output

Print two integers — the minimum and maximum possible value of f can be made from valid assignment of given tree. Note that it's always possible to make an assignment under given constraints.

Examples

Input


6
1 3
2 3
3 4
4 5
5 6


Output


1 4


Input


6
1 3
2 3
3 4
4 5
4 6


Output


3 3


Input


7
1 2
2 7
3 4
4 7
5 6
6 7


Output


1 6

Note

In the first example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum. 

<image>

In the second example, possible assignments for each minimum and maximum are described in picture below. The f value of valid assignment of this tree is always 3. 

<image>

In the third example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum. 

<image>
import sys
sys.setrecursionlimit(11000)

_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__

def go():
    n = int(input())
    if n==2:
        return '1 1'
    # n,l,r = map(int, input().split())
    # a = list(map(int, input().split()))

    e = {i: set() for i in range(1, n + 1)}
    rank = [0] * (n + 1)
    root=-1
    for _ in range(n - 1):
        a, b = map(int, input().split())
        e[a].add(b)
        e[b].add(a)
        rank[a] += 1
        rank[b] += 1
        if rank[a]>1:
            root=a
        if rank[b]>1:
            root=b

    mx = n-1
    for a in range(1,n+1):
        cnt=sum(rank[b]==1 for b in e[a])
        mx-=max(0,cnt-1)

    ev,od = False,False
    que=[root]
    i=0
    dep = [0]*(n+1)
    done = {root}
    while i<len(que):
        v = que[i]
        if len(e[v])==1:
            if dep[v]%2==0:
                ev=True
            if dep[v]%2==1:
                od=True
        for w in e[v]:
            if w not in done:
                que.append(w)
                dep[w]=dep[v]+1
                done.add(w)

        i+=1
    if ev and od:
        mn=3
    else:
        mn=1

    return f'{mn} {mx}'

    #
    # hei = [-1]*(n+1)
    # def dfs(v,par):
    #     if len(e[v])==1:
    #         hei[v]=0
    #     else:
    #         hei[v]=min(dfs(w,v) for w in e[v] if w!=par)+1
    #     return hei[v]
    #
    # dfs(root,-1)
    # # print (hei)
    #
    # kolej = sorted((i for i in range(1,n+1) if rank[i]>1),key=hei.__getitem__)
    # print (kolej)
    #
    # res=0
    # for v in kolej:
    #     if rank[v]
    #

    # que = [i for i in range(1, n + 1) if rank[i] == 1]
    # dep = [0 if rank[i] == 1 else -1 for i in range(0, n + 1)]
    # index = 0
    # while index < len(que):
    #     cur = que[index]
    #     curd = dep[cur]
    #     for b in e[cur]:
    #         if dep[b] < 0:
    #             dep[b] = curd + 1
    #             que.append(b)
    #     index += 1
    # print(dep)
    # kolej = sorted(range(1, n + 1), key=dep.__getitem__)


# x,s = map(int,input().split())
# t = int(input())
t = 1
ans = []
for _ in range(t):
    # print(go())
    ans.append(str(go()))
#
print('\n'.join(ans))
