Submission #6919866

---

Source Code Expand

import sys
sys.setrecursionlimit(10**7)


n = int(input())
edge = {}
for i in range(n):
    a, b = map(int, input().split())
    if a in edge:
        edge[a].append(b)
    else:
        edge[a] = [b]

    if b in edge:
        edge[b].append(a)
    else:
        edge[b] = [a]

visited = []
def dfs(now, prev):
    if now in visited:
        print_ans(len(visited) - visited.index(now))
        exit()
    else:
        for e in edge[now]:
            if e == prev:
                continue
            visited.append(now)
            ret = dfs(e, now)
            visited.pop()
    return

def print_ans(length):
    ans_min = 1
    ans_max = n
    if length == n:
        ans_min = 2
        
    if length % 2 == 1:
        ans_max = n-1
        
    print(str(ans_min) + ' ' + str(ans_max))
    
dfs(1, 1)

Submission Info

Judge Result