paiza ダンジョンのデッドロック 3 未完

※いくつかのテストケースでタイムオーバーとなり解けませんでした。
どうも実力不足のようなので分かり次第修正します。

N,M = input().split()
M = int(M)
ini,pend,ans,seq = [],[],[],[]
flg = 0

for i in range(M):
    ini.append(input().split())
    
for i in range(M):
    ini[i].insert(0,str(i+1))
    
seq = ini[0]
end = ini[-1]

while flg == 0:    
    for idx,elem in enumerate(ini):
        if seq[1] == seq[2]:
            pend.append(seq)
            flg = 1
            break

        if seq[2] == elem[1] and seq != elem:
            pend.append(seq)
            seq = elem
            break

        if end == elem:
            pend.append(seq)
            flg =1
               
for pend_elem in pend[::-1]:
    ans.append(int(pend_elem[0]))
    
print(*ans)