問題はこちら。

最少の長さの閉路を求めればよい。多重辺のない有向グラフなのでe = (a, b)とすればbから出発してaに戻る最小パスをBFSで求めれば、eを含むループの中で最小のものが求められる。このようなループをeについて全て求め最小の閉路の長さを見つける。最後に最小ループを再構築する。

import sys
from collections import deque
readline = sys.stdin.readline


def main():
 N, M = map(int, readline().split())
 G = [[] for _ in range(N)]
 E = []
 for _ in range(M):
   a, b = map(int, readline().split())
   a -= 1; b -= 1
   G[a].append(b)
   E.append((a, b))

 e = None
 min_ = N + 1
 for a, b in E:
   prev = [-1] * N
   q = deque([b])
   prev[b] = a
   while q:
     x = q.popleft()
     for y in G[x]:
       if prev[y] >= 0:
         continue
       prev[y] = x
       q.append(y)
   if prev[a] == -1:
     continue
   tmp = 1
   p = prev[a]
   while p != a:
     tmp += 1
     p = prev[p]
   if min_ > tmp:
     min_ = tmp
     e = (a, b)

 if min_ == N + 1:
   print(-1)
   return

 a, b = e
 prev = [-1] * N
 q = deque([b])
 prev[b] = a
 while q:
   x = q.popleft()
   for y in G[x]:
     if prev[y] >= 0:
       continue
     prev[y] = x
     q.append(y)

 ans = [a]
 p = prev[a]
 while p != a:
   ans.append(p)
   p = prev[p]
 print(len(ans))
 for x in ans:
   print(x + 1)


if __name__ == '__main__':
 main()