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 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 \le n \le 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 \le a_{i} \lt b_{i} \le 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]

Difficulty: competition

Starter code:

Solutions:
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    u,v = [int(i)-1 for i in input().split()]
    g[u].append(v)
    g[v].append(u)

leaf = [len(i)==1 for i in g]
root = -1
mx = n-1
for i in range(n):
    if leaf[i]:
        root = i
    leafs = 0
    for j in g[i]:
        if leaf[j]:
            leafs += 1
    if leafs > 1:
        mx -= leafs-1

stack = [(root, -1, 0)]
even = True
while len(stack)>0:
    i, j, d = stack.pop()
    if leaf[i] and d%2 == 1:
        even = False
        break
    for k in g[i]:
        if k != j:
            stack.append((k,i,d+1))
mn = 1 if even else 3

print(mn,mx)


import sys
input = sys.stdin.readline

n=int(input())
E=[[] for i in range(n+1)]

for i in range(n-1):
    a,b=list(map(int,input().split()))
    E[a].append(b)
    E[b].append(a)

LEAF=[]
for i in range(n+1):
    if len(E[i])==1:
        LEAF.append(i)

Q=[1]
USE=[-1]*(n+1)
USE[1]=0

while Q:
    x=Q.pop()
    for to in E[x]:
        if USE[to]==-1:
            USE[to]=1-USE[x]
            Q.append(to)

f=USE[LEAF[0]]

for l in LEAF:
    if f!=USE[l]:
        MIN=3
        break
else:
    MIN=1

#print(MIN)

MAX=n-1

FP=[0]*(n+1)

for l in LEAF:
    for to in E[l]:
        if FP[to]==1:
            MAX-=1
        else:
            FP[to]=1

print(MIN,MAX)
    


import sys
input = sys.stdin.readline

n = int(input())

neigh = [[] for i in range(n)]
l = []
for i in range(n - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    neigh[a].append(b)
    neigh[b].append(a)
    l.append((a,b))

#Max
edges = set()
for a, b in l:
    if len(neigh[a]) == 1:
        a = -1
    if len(neigh[b]) == 1:
        b = -1
    if a > b:
        a, b = b, a
    edges.add((a,b))

MAX = len(edges)

#Min
leafDepth = []
visited = [False] * n
from collections import deque
q = deque()
q.append((0,0))
while q:
    nex, d = q.popleft()
    if not visited[nex]:
        visited[nex] = True

        if len(neigh[nex]) == 1:
            leafDepth.append(d)
        for v in neigh[nex]:
            q.append((v,d+1))

MIN = 1
corr = leafDepth.pop() % 2
for d in leafDepth:
    if d % 2 != corr:
        MIN = 3 
        


#Out
print(MIN, MAX)


import sys

n = int(sys.stdin.readline().strip())
N = [[] for i in range (0, n)]
C = [-1 for i in range (0, n)]
for i in range (0, n-1):
    a, b = list(map(int,sys.stdin.readline().strip().split()))
    a, b = a-1, b-1
    N[a].append(b)
    N[b].append(a)
C[0] = 0
L0 = [0]
L1 = []
while len(L0) + len(L1) > 0:
    for i in L0:
        for j in N[i]:
            if C[j] == -1:
                C[j] = 1
                L1.append(j)
    L0 = []
    for i in L1:
        for j in N[i]:
            if C[j] == -1:
                C[j] = 0
                L0.append(j)
    L1 = []
f = 1
F = n-1
L = []
M = []
for i in range (0, n):
    if len(N[i]) == 1:
        L.append(N[i])
        M.append(i)
L.sort()
for i in range (0, len(L)-1):
    if L[i] == L[i+1]:
        F = F - 1
    if C[M[i]] != C[M[i+1]]:
        f = 3
print(f, F)

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]

tree = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    
max_ = n - 1
for v in range(n):
    cnt = 0
    for nxt_v in tree[v]:
        if len(tree[nxt_v]) == 1:
            cnt += 1
    max_ -= max(cnt - 1, 0)
    
    
visited = [-1] * n
q = deque([0])
visited[0] = 0
while q:
    v = q.popleft()
    for nxt_v in tree[v]:
        if visited[nxt_v] != -1:
            continue
        visited[nxt_v] = visited[v] + 1
        q.append(nxt_v)


min_ = 3
for i in range(n):
    if len(tree[i]) == 1:
        if visited[i] % 2 == 0:
            break
else:
    min_ = 1

for i in range(n):
    if len(tree[i]) == 1:
        if (visited[i] + 1) % 2 == 0:
            break
else:
    min_ = 1
print(min_, max_)