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>
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------- fast io --------------------
#consider parity of path lengths
#get the parity easily by finding the depth of nodes
#there are key nodes they must be a certain number at
#bfs from that keynode and look at the distances from it, then thats ur answer
from collections import deque,defaultdict
n=int(input());tree=[[] for s in range(n)]
for s in range(n-1):
    u,v=map(int,input().split())
    u-=1;v-=1
    tree[u].append(v);tree[v].append(u)
root=0
for s in range(n):
    if len(tree[s])>1:
        root=s;break
#finding the depth
queue=deque([root]);vis=set([root]);depth=0;cv=1
depths=defaultdict(list);dd={}
depths[depth].append(root);dd[root]=depth
while len(queue)>0:
    v0=queue.popleft()
    for s in tree[v0]:
        if not(s in vis):
            queue.append(s);vis.add(s)
    cv-=1;depths[depth].append(v0);dd[v0]=depth
    if cv==0:
        depth+=1;cv=len(queue)
odd=0;even=0;leaf=set([]);dist=[]
for s in range(n):
    if len(tree[s])==1:
        leaf.add(s);dist.append(dd[s])
        odd+=dd[s]%2;even+=(dd[s]%2+1)%2
totodd=odd*even;toteven=(odd*(odd-1))//2+(even*(even-1))//2
minnum=1+min(1,totodd)*2
depth-=1;dict1=defaultdict(int);ans=0
while depth>0:
    for s in depths[depth]:
        if s in leaf:
            for i in tree[s]:
                if dd[i]<depth:
                    ans+=1;dict1[i]+=1
                    if dict1[i]>1:
                        ans-=1
        else:
            for i in tree[s]:
                if dd[i]<depth:
                    ans+=1
    depth-=1
print(minnum,ans)