Submission #487630

---

Source Code Expand

# -*- coding: utf-8 -*-

N = int(raw_input())

graph = [[] for i in range(N)]

for i in range(N):
    a = map(int, raw_input().split())
    graph[a[0]-1].append(a[1]-1)
    graph[a[1]-1].append(a[0]-1) #0 - N-1で考える


def find_loop(start, before, past):
    position = start
    root = past
    for i in graph[position]:
        if i != before:
            if i in root:
                root.append(i)
                return root #ループ発見
            else:
                root.append(i)
                return find_loop(i, position, root)
                position = i
        else:
            pass
    return None

def complete_loop(list):
    char = list[-1]
    num = list.index(char)
    return list[num:-1]


loop = complete_loop(find_loop(0, 0, [0]))

max = 0
min = 0
if len(loop) == N:
    min = 2
else:
    min = 1

if len(loop) % 2 == 0:
    max = N
else:
    max = N-1

print str(min) + ' ' + str(max)

Submission Info

Judge Result