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>
from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def main():
    
    # ans=[]
    # import itertools
    # n=6
    # for c in itertools.combinations_with_replacement(range(1,40),n):
    #     temp=0
    #     for x in c:
    #         temp^=x
    #     if temp==0 and len(set(c))>len(set(ans)):
    #         ans=c
    # print(ans)
    
    
    # For minimum, if any pair of leaves have odd edge counts between them,
    # ans is 3. Else if all even edge counts, ans is 1.
    # For maximum, every edge can contribute, except for nodes connected to
    # more than 1 leaf. Only 1 leaf-edge can be used.
    
    n=int(input())
    adj=[[] for _ in range(n+1)]
    for _ in range(n-1):
        a,b=readIntArr()
        adj[a].append(b)
        adj[b].append(a)
    
    #Root the tree at a non-leaf
    for node in range(1,n+1):
        if len(adj[node])>1:
            root=node
            break
    
    @bootstrap
    def dfs(node,parent): #return [has oddParity, has evenParity]
        ret=[False,False]
        if len(adj[node])==1: #leaf, length is 0 so even.
            ret[1]=True
        else:
            for node2 in adj[node]:
                if node2!=parent:
                    childHasOdd,childHasEven=(yield dfs(node2,node))
                    ret[0]=childHasEven or ret[0] #swap even/odd every level
                    ret[1]=childHasOdd or ret[1]
        yield ret
    
    hasOdd,hasEven=dfs(root,-1)
    if hasOdd and hasEven: #if at any node there is both odd and even distances from 2 leaves, then the 2 leaves have odd edges between them
        minAns=3
    else:
        minAns=1
    
    allLeaves=[]
    for node in range(1,n+1):
        if len(adj[node])==1:
            allLeaves.append(node)
    nodeLeafConnections=[0 for _ in range(n+1)]
    for leaf in allLeaves:
        nodeLeafConnections[adj[leaf][0]]+=1
    
    maxAns=n-1
    for cnt in nodeLeafConnections:
        maxAns-=max(0,cnt-1)
    
    print('{} {}'.format(minAns,maxAns))
    
    return
    
#import sys
#input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
import sys
input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.
 
def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
 
inf=float('inf')
MOD=10**9+7
 
main()