ダンジョンのデッドロック 3 Python3編

N,M = map(int,input().split())

room = [-1]*(N+1)
req_l = [-1]*(M+1)

ans = []

for i in range(M):
    a,b = map(int,input().split())
    room[a] = i+1
    req_l[i+1] = b
    
p = 1
q = req_l[p]

while True:

    if room[q] == -1:
        ans.append(p)
        break
    
    elif p == room[q] and p==1:
        ans.append(p)
        break

    elif p == room[q]:
        p += 1
    
    ans.append(p)
    p = room[q]
    q = req_l[p]
       
print(*ans[::-1])