Submission #6919636

---

Source Code Expand

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)


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

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

loop_length = dfs(1, 1)
ans_min = 1
ans_max = n
if loop_length == n:
    ans_min = 2

if loop_length % 2 == 1:
    ans_max = n-1

print(str(ans_min) + ' ' + str(ans_max))

Submission Info

Judge Result