Problem:


Score : 600 points

Problem Statement

Given is a directed graph G with N vertices and M edges.

The vertices are numbered 1 to N, and the i-th edge is directed from Vertex A_i to Vertex B_i.

It is guaranteed that the graph contains no self-loops or multiple edges.

Determine whether there exists an induced subgraph (see Notes) of G such that the in-degree and out-degree of every vertex are both 1. If the answer is yes, show one such subgraph.

Here the null graph is not considered as a subgraph.

Notes

For a directed graph G = (V, E), we call a directed graph G' = (V', E') satisfying the following conditions an induced subgraph of G:

V' is a (non-empty) subset of V.

E' is the set of all the edges in E that have both endpoints in V'.

Constraints

1 \leq N \leq 1000

0 \leq M \leq 2000

1 \leq A_i,B_i \leq N

A_i \neq B_i

All pairs (A_i, B_i) are distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
:
A_M B_M

Output

If there is no induced subgraph of G that satisfies the condition, print -1.
Otherwise, print an induced subgraph of G that satisfies the condition, in the following format:

K
v_1
v_2
:
v_K

This represents the induced subgraph of G with K vertices whose vertex set is \{v_1, v_2, \ldots, v_K\}. (The order of v_1, v_2, \ldots, v_K does not matter.)
If there are multiple subgraphs of G that satisfy the condition, printing any of them is accepted.

Sample Input 1

4 5
1 2
2 3
2 4
4 1
4 3

Sample Output 1

3
1
2
4

The induced subgraph of G whose vertex set is \{1, 2, 4\} has the edge set \{(1, 2), (2, 4), (4, 1)\}. The in-degree and out-degree of every vertex in this graph are both 1.

Sample Input 2

4 5
1 2
2 3
2 4
1 4
4 3

Sample Output 2

-1

There is no induced subgraph of G that satisfies the condition.

Sample Input 3

6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2

Sample Output 3

4
2
3
4
5



Sample input:
4 5
1 2
2 3
2 4
4 1
4 3


Sample output:
3
1
2
4

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
g=[[] for i in range(n+1)]
for a,b in ab:
  g[a].append(b)
st=0
for i in range(1,n+1):
  vis=[0]*(n+1)
  q=deque([i])
  while q:
    x=q.popleft()
    if vis[x]==1:
      st=x
      break
    vis[x]=1
    for y in g[x]:
      q.append(y)
  if st:
    break
if st==0:
  print(-1)
  exit()
q=deque([st])
route=[[] for i in range(n+1)]
ans = 0
while q:
  x=q.popleft()
  for y in g[x]:
    route[y].extend(route[x])
    route[y].append(x)
    q.append(y)
    if route[y][0]==y:
      ans=route[y]
      break
  if ans:
    break
print(len(ans))
print(*ans,sep="\n")

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
g=[[] for i in range(n+1)]
for a,b in ab:
  g[a].append(b)
vis=[0]*(n+1)
st=0
for i in range(1,n+1):
  q=deque([i])
  while q:
    x=q.popleft()
    if vis[x]==1:
      st=x
      break
    vis[x]=1
    for y in g[x]:
      q.append(y)
  if st:
    break
if st==0:
  print(-1)
  exit()
q=deque([st])
route=[[] for i in range(n+1)]
ans = 0
while q:
  x=q.popleft()
  for y in g[x]:
    route[y].extend(route[x])
    route[y].append(x)
    q.append(y)
    if route[y][0]==y:
      ans=route[y]
      break
  if ans:
    break
print(len(ans))
print(*ans,sep="\n")

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
g=[[] for i in range(n+1)]
for a,b in ab:
  g[a].append(b)
vis=[0]*(n+1)
st=0
for i in range(1,n+1):
  q=deque([i])
  while q:
    x=q.popleft()
    if vis[x]==1:
      st=x
      break
    vis[x]=1
    for y in g[x]:
      q.append(y)
  if st:
    break
if st==0:
  print(-1)
  exit()
q=deque([st])
route=[[] for i in range(n+1)]
while q:
  x=q.popleft()
  for y in g[x]:
    route[y].extend(route[x])
    route[y].append(x)
    q.append(y)
  if route[y][0]==y:
    ans=route[y]
    break
print(len(ans))
print(*ans,sep="\n")

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
g=[[] for i in range(n+1)]
for a,b in ab:
  g[a].append(b)
vis=[0]*(n+1)
st=0
for i in range(1,n+1):
  q=deque([i])
  while q:
    x=q.popleft()
    if vis[x]==1:
      st=x
      break
    vis[x]=1
    for y in g[x]:
      q.append(y)
  if st:
    break
if st==0:
  print(-1)
  exit()
q=depue([st])
route=[[] for i in range(n+1)]
while q:
  x=q.popleft()
  for y in g[x]:
    if route[y][0]==y:
      ans=route[y]
      break
    else:
      route[y].append(x)
      q.append(y)
print(len(ans))
print(*ans,sep="\n")

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

read = sys.stdin.read

N, M = map(int, input().split())
if M != 0:
    AB = list(map(int, read().split()))
else:
    print(-1)
    exit()

graph = [[] for _ in range(N + 1)]
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)

for i in A_s:
    if not graph[i]:
        print(-1)
        exit()

stack = [i for i in range(1, N + 1) if len(graph[i]) == 1]
answer = []
while stack:
    v = stack.pop()
    queue = deque([(v, [v])])
    while queue:
        v_1, route = queue.popleft()
        for i in graph[v_1]:
            if i in route:
                route = route[route.index(i):]
                answer.append((len(route), route))
            else:
                queue.append((i, route + [i]))

K, a = min(answer)
print(K)
print('\n'.join(map(str, a)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
n,m=map(int,input().split())
es=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
path=[]
def dfs(v,w,z):
    if w==v:
        if z:
            path.append(v)
            return True
        else:
            z=True
    ans=False
    for i in es[v]:
        if sw:
            ans=ans or dfs(i,w,z)
    if ans:
        path.append(v)
    return ans
for i in range(n):
    sw=[False]*n
    if dfs(i,i,False):
        print(len(path)-1)
        for i in range(len(path)-2,-1,-1):
            print(path[i]+1)
        exit()
print(-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
n,m=map(int,input().split())
es=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
path=[]
def dfs(v,w,z):
    if w==v:
        if z:
            path.append(v)
            return True
        else:
            z=True
    ans=False
    for i in es[v]:
        if sw:
            ans=ans or dfs(i,w,z)
    if ans:
        path.append(v)
    return ans
for i in range(n):
    sw=[False]*n
    if dfs(i,i,False):
        print(len(path))
        for i in range(len(path)-2,-1,-1):
            print(path[i]+1)
        exit()
print(-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
if M == 0:
  print(1)
  print(1)
  exit(0)
e = dd(list)
reve = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  reve[v].append(u)
vis = set()
inc = [0] * (N + 1)
def dfs(x, l):
  global vis
  global inc
  vis.add(x)
  ok = 0
  for y in reve[x]:
    if y in vis: inc[x] += 1
  if inc[x] > 1:
    inc[x] = 0
    vis.discard(x)
    return
  for y in e[x]:
    if y == l:
      ok = 1
      continue
    if y in vis:
      inc[x] = 0
      vis.discard(x)
      return
  if ok:
    print(len(vis))
    for v in vis: print(v)
    #print(vis, inc)
    exit(0)
  for y in e[x]:
    dfs(y, l)
  vis.discard(x)

for s in range(1, N + 1):
  dfs(s, s)
print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

n,m = map(int,input().split())
G = [list() for _ in range(n+1)]
R = [list() for _ in range(n+1)]
for _ in range(m):
  u,v = map(int,input().split())
  G[u].append(v)
  R[v].append(u)

def find_cycle(visited = [1]):
  v = visited[-1]
  for x in G[v]:
    if x in visited:
      return visited[visited.index(x):]
    res = find_cycle(visited + [x])
    if len(res) > 0:
      return res
  return list()

def trash(i):
  dis = [n]*(n+1)
  dis[i] = 0
  q = deque([i])
  while q:
    v = q.popleft()
    for x in G[v]:
      if x == i: continue
      if dis[x] < dis[v] + 1:
        # print(dis,i,v,x)
        return v
      dis[x] = dis[v] + 1
      q.append(x)
  return False

for i in range(1,n+1):
  cyc = find_cycle([i])
  if cyc: break
  else: print(-1); exit(0)

while True:
  # print(cyc)
  for i in range(1,n+1):
    if i not in cyc:
      for x in G[i]:
        R[x].remove(i)
      G[i] = []
      for x in R[i]:
        G[x].remove(i)
      R[i] = []
     
  for i in cyc:
    if len(G[i]) > 1:
      st = i
      v = trash(st)
      for x in G[v]:
        R[x].remove(v)
      G[v] = []
      for x in R[v]:
        G[x].remove(v)
      R[v] = []
      # print(G)
      # print(R)
      cyc = set(find_cycle([st]))
      break
  else: break
if not cyc: print(-1); exit(0)     
print(len(cyc))
print(*cyc, sep='\n')

Submission status: Runtime Error

Solution code:
from collections import deque

n,m = map(int,input().split())
G = [list() for _ in range(n+1)]
R = [list() for _ in range(n+1)]
for _ in range(m):
  u,v = map(int,input().split())
  G[u].append(v)
  R[v].append(u)

def find_cycle(visited = [1]):
  v = visited[-1]
  for x in G[v]:
    if x in visited:
      return visited[visited.index(x):]
    res = find_cycle(visited + [x])
    if len(res) > 0:
      return res
  return list()

def trash(i):
  dis = [n]*(n+1)
  dis[i] = 0
  q = deque([i])
  while q:
    v = q.popleft()
    for x in G[v]:
      if x == i: continue
      if dis[x] < dis[v] + 1:
        # print(dis,i,v,x)
        return v
      dis[x] = dis[v] + 1
      q.append(x)
  return False

for i in range(1,n+1):
  cyc = find_cycle([i])
  if cyc: break
  else: print(-1); exit(0)

while True:
  # print(cyc)
  for i in range(1,n+1):
    if i not in cyc:
      for x in G[i]:
        R[x].remove(i)
      G[i] = []
      for x in R[i]:
        G[x].remove(i)
      R[i] = []
     
  for i in cyc:
    if len(G[i]) > 1:
      st = i
      v = trash(st)
      for x in G[v]:
        R[x].remove(v)
      G[v] = []
      for x in R[v]:
        G[x].remove(v)
      R[v] = []
      # print(G)
      # print(R)
      cyc = set(find_cycle([st]))
      break
  else: break
      
print(len(cyc))
print(*cyc, sep='\n')

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

compo = []
cs = []
N = 0
M = 0
A = None
B = None
E = None

def main():
    global compo,cs,N,M,A,B,E
    N, M = rip()
    A = [0] * M
    B = [0] * M
    for i in range(M):
        A[i], B[i] = rip()
        A[i] -= 1
        B[i] -= 1
    
    E = [[] for i in range(N)]
    for i in range(M):
        E[A[i]].append(B[i])
    
    compo = [-1] * N

    def dfs(cmp, route, hs):
        global compo,cs,N,M,A,B,E
        if(len(cs) > 0) : return
        now = route[len(route) - 1]
        for nxt in E[now]:
            if compo[nxt] == -1:
                compo[nxt] = cmp
                route.append(nxt)
                hs.add(nxt)
                dfs(cmp, route, hs)
                hs.remove(nxt)
                route.pop(-1)
            elif compo[nxt] == cmp:
                if nxt in hs:
                    cs = route[route.index(nxt):]
                return
            else:
                return


    cs = []
    c = 0
    for i in range(N):
        if(compo[i] != -1): continue
        c += 1
        a = []
        hs = set()
        a.append(i)
        hs.add(i)
        compo[i] = c
        dfs(c, a, hs)

    if len(cs) == 0:
        print(-1)
        sys.exit(0)
    
    l = cs
    while(True):
        di = dict()
        for i in range(len(l)):
            di[l[i]] = l[(i + 1) % len(l)]
        edx = -1
        for i in range(M):
            if A[i] in di and B[i] in di:
                if di[A[i]] != B[i]:
                    edx = i
                    break
        
        if edx == -1:
            print(len(l))
            print("\n".join([str(n + 1) for n in l]))
            sys.exit(0)
        
        di[A[edx]] = B[edx]
        nl = [A[edx], B[edx]]
        while True:
            nxt = di[nl[-1]]
            if nxt != nl[0]:
                nl.append(nxt)
            else:
                break
        l = nl

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

compo = []
cs = []
N = 0
M = 0
A = None
B = None
E = None

def main():
    global compo,cs,N,M,A,B,E
    N, M = rip()
    A = [0] * M
    B = [0] * M
    for i in range(M):
        A[i], B[i] = rip()
        A[i] -= 1
        B[i] -= 1
    
    E = [[] for i in range(N)]
    for i in range(M):
        E[A[i]].append(B[i])
    
    compo = [-1] * N

    def dfs(cmp, route, hs):
        global compo,cs,N,M,A,B,E
        if(len(cs) > 0) : return
        now = route[len(route) - 1]
        for nxt in E[now]:
            if compo[nxt] == -1:
                compo[nxt] = cmp
                route.append(nxt)
                hs.add(nxt)
                dfs(cmp, route, hs)
                hs.remove(nxt)
                route.pop(-1)
            elif compo[nxt] == cmp:
                if nxt in hs:
                    cs = route[route.index(nxt):]
                return
            else:
                return



    c = 0
    for i in range(N):
        if(compo[i] != -1): continue
        a = []
        hs = set()
        a.append(i)
        hs.add(i)
        compo[i] = c
        dfs(c, a, hs)
        c += 1

    if len(cs) == 0:
        print(-1)
        sys.exit(0)
    
    l = cs
    while(True):
        di = dict()
        for i in range(len(l)):
            di[l[i]] = l[(i + 1) % len(l)]
        edx = -1
        for i in range(M):
            if A[i] in di and B[i] in di:
                if di[A[i]] != B[i]:
                    edx = i
                    break
        
        if edx == -1:
            print(len(l))
            print("\n".join([str(n + 1) for n in l]))
            sys.exit(0)
        
        di[A[edx]] = B[edx]
        nl = [A[edx], B[edx]]
        while True:
            nxt = di[nl[-1]]
            if nxt != nl[0]:
                nl.append(nxt)
            else:
                break
        l = nl

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

compo = []
cs = []
N = 0
M = 0
A = None
B = None
E = None

def main():
    global compo,cs,N,M,A,B,E
    N, M = rip()
    A = [0] * M
    B = [0] * M
    for i in range(M):
        A[i], B[i] = rip()
        A[i] -= 1
        B[i] -= 1
    
    E = [[] for i in range(N)]
    for i in range(M):
        E[A[i]].append(B[i])
    
    compo = [-1] * N

    def dfs(cmp, route, hs):
        global compo,cs,N,M,A,B,E
        if(len(cs) > 0) : return
        now = route[len(route) - 1]
        for nxt in E[now]:
            if compo[nxt] == -1:
                compo[nxt] = cmp
                route.append(nxt)
                hs.add(nxt)
                dfs(cmp, route, hs)
                hs.remove(nxt)
                route.pop(-1)
            elif compo[nxt] == cmp:
                if nxt in hs:
                    cs = route[route.index(nxt):]
                return
            else:
                return



    c = 0
    for i in range(N):
        if(compo[i] != -1): continue
        a = []
        hs = set()
        a.append(i)
        hs.add(i)
        compo[i] = c
        dfs(c, a, hs)

    if len(cs) == 0:
        print(-1)
        sys.exit(0)
    
    l = cs
    while(True):
        di = dict()
        for i in range(len(l)):
            di[l[i]] = l[(i + 1) % len(l)]
        edx = -1
        for i in range(M):
            if A[i] in di and B[i] in di:
                if di[A[i]] != B[i]:
                    edx = i
                    break
        
        if edx == -1:
            print(len(l))
            print("\n".join([str(n + 1) for n in l]))
            sys.exit(0)
        
        di[A[edx]] = B[edx]
        nl = [A[edx], B[edx]]
        while True:
            nxt = di[nl[-1]]
            if nxt != nl[0]:
                nl.append(nxt)
            else:
                break
        l = nl

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from itertools import product, permutations, combinations
from time import time

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

q = list(range(N))
c = defaultdict(int)
t = [0]*N
r = 0
a = time()

while q:
    b = time()
    if b - a > 0.9:
        print(N*(N-1)//2)
        exit()
    r += 1
    nq = []
    for i in q:
        j = A[i][t[i]] - 1
        k = i
        if k < j:
            j, k = k, j
        c[(j, k)] += 1
        if c[(j, k)] == 2:
            t[j] += 1
            t[k] += 1
            if t[j] < N-1:
                nq.append(j)
            if t[k] < N-1:
                nq.append(k) 
    q = nq

for tt in t:
    if tt != N-1:
        print(-1)
        exit()

print(r)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
table = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    table[a-1].append(b-1)

visit = [False] * N
visit2 = [False] * N
g = []


def dfs(v):
    g.append(v)
    if visit[v]:
        return True
    visit[v] = True
    visit2[v] = True
    for u in table[v]:
        if dfs(u):
            return True
    g.pop()
    visit[v] = False
    return False


for i in range(N):
    g = []
    if not visit2[i]:
        if dfs(i):
            break
else:
    print(-1)
    exit()
print(0)
# ans = [v+1 for v in g[g.index(g[-1]):-1]]
# print(len(ans))
# print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
table = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    table[a-1].append(b-1)

visit = [False] * N
visit2 = [False] * N
g = []


def dfs(v):
    g.append(v)
    if visit[v]:
        return True
    visit[v] = True
    visit2[v] = True
    for u in table[v]:
        if dfs(u):
            return True
    g.pop()
    visit[v] = False
    return False


for i in range(N):
    g = []
    if not visit2[i]:
        if dfs(i):
            break
else:
    print(-1)
    exit()

ans = [v+1 for v in g[g.index(g[-1]):-1]]
print(len(ans))
print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
table = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    table[a-1].append(b-1)

visit = [False] * N
visit2 = [False] * N
g = []


def dfs(v):
    g.append(v)
    if visit[v]:
        return True
    visit[v] = True
    visit2[v] = True
    for u in table[v]:
        if dfs(u):
            return True
    g.pop()
    visit[v] = False
    return False


for i in range(N):
    g = []
    if not visit2[i]:
        if dfs(i):
            break
else:
    print(-1)
    exit()

print(*[v+1 for v in g[g.index(g[-1]):-1]], sep="\n")

Submission status: Runtime Error

Solution code:
def bellman_ford(s,v,e,es):
    #s:始点　v:頂点数　e:辺の数　es:[s,t,c]
    d = [float("inf")]*v
    d[s] = 0
    used=[0]*v
    tf=0
    for i in range(n*2):
        for p,q,r in es:
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                used[p]+=1
                if i>=n-1:
                    tf=1

    return tf,used


n,m=map(int,input().split())
es=[]
l=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    es.append((a,b,-1))
    l[b].append(a)

f,ll=bellman_ford(0,n,m,es)
if not f:
    print(-1)
    exit()

x=ll.index(max(ll))
ans=set()
ans.add(x)
while True:
    to=l[x][0]
    if to in ans:
        break
    ans.add(to)
    x=to
ans=list(ans)
print(len(ans))
print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return [int(i)-1 for i in input().split()]
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    ans = 0
    for i in range(1, n + 1):
        ans += i & 1
    print(ans/n)
    return

#B
def B():
    _, k = LI()
    h = LI()
    ans = 0
    for i in h:
        ans += i >= k
    print(ans)
    return

#C
def C():
    n = II()
    a = LI()
    d = defaultdict(int)
    for i in range(n):
        d[a[i] + 1] = i + 1
    for _, v in sorted(d.items()):
        print(v, end=" ")
    print()
    return

def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    """ 6以上の数であれば p (素数) <= n のlistを返す """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

#D
def D():
    a, b = LI()
    da = defaultdict(int)
    db = defaultdict(int)
    for i in range(2, int(math.sqrt(a)) + 1):
        while a % i == 0:
            a = a // i
            da[i] = 1
        while b % i == 0:
            b = b // i
            db[i] = 1
    da[a] = 1
    db[b] = 1
    da[1] = 1
    db[1] = 1
    print(len(set(da.keys()) & set(db.keys())))
    return

#E
def E():
    n, m = LI()
    dp = [inf] * (1 << n)
    dp[0] = 0
    for _ in range(m):
        a, b = LI()
        c = LI_()
        fulls = sum((1<<c[i] for i in range(b)))
        for i in range(1 << n):
            dp[i | fulls] = min(dp[i | fulls], dp[i] + a)
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])
    return

#F
def F():
    n,m = LI()
    edg = [[] for i in range(n)]
    redg = [[] for i in range(n)]
    
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        redg[b].append(a)

    def dijkstra(start):
        dist = [inf] * n
        dist[start] = 0
        q = [(0,start)]
        while q:
            du, u = heappop(q)
            for i in edg[u]:
                if du + 1 < dist[i]:
                    dist[i] = du + 1
                    heappush(q, (du + 1, i))
        return dist
    
    d = [None] * n
    for i in range(n):
        d[i] = dijkstra(i)

    tmp = inf
    tt = None
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if tmp > d[i][j] + d[j][i]:
                tt = (i, j)
                tmp = d[i][j] + d[j][i]

    if tmp:
        print(tmp)
        s, g = tt
        ans1 = [s]
        ans2 = [g]
        q = deque([s])

        while q:
            a = q.pop()
            for ai in redg[a]:
                if g != ai and d[g][ai] + 1 == d[g][a]:
                    ans1.append(ai)
                    q.append(ai)
                    break
        q = deque([g])
        while q:
            a = q.pop()
            for ai in redg[a]:
                if s != ai and d[s][ai] + 1 == d[s][a]:
                    ans2.append(ai)
                    q.append(ai)
                    break
        ans = ans1 + ans2
        for a in ans:
            print(a+1)

    else:
        print(-1)
    return

#Solve
if __name__ == '__main__':
    F()

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
uv = [ set() for _ in range(N)]
vu = [ set() for _ in range(N)]
for _ in range(M):
    A, B = inpl()
    uv[A-1].add(B-1)
    vu[B-1].add(A-1)

EMPTY, LOOP, TREE = 0, 1, 2
ENTER, EXIT = 0, 1
status = [EMPTY] * N
for s in range(N):
    states_pool = [(s,[],ENTER)]
    while states_pool:
        u, chain, flag = states_pool.pop()
        if flag == EXIT or status[u] == TREE:
            status[u] = TREE
            continue
        elif status[u] == LOOP:
            break
        else: # ENTER, EMPTY
            status[u] = LOOP
            states_pool.append((u,chain,EXIT))
            new_chain = chain.copy()
            new_chain.append(u)
            for c in uv[u]:
                states_pool.append((c, new_chain, ENTER))
    else:
        continue
    break
else:
    print(-1)

n = 0
while chain[n] != u:
    n += 1
chain = chain[n:]
L = len(chain)
nextnode = [None]*N
for i in range(L-1):
    nextnode[chain[i]] = chain[i+1]
nextnode[chain[L-1]] = chain[0]
pos = [None]*N
for p in range(len(chain)):
    pos[chain[p]] = p
i = 0
while i < L:
    h = 1
    c = chain[(i+1)%L]
    for j in uv[chain[i % L]]:
        p = pos[j]
        if p is None:
            continue
        else:
            if (p-i)%L > h:
                h = (p-i)%L
                c = j
    nextnode[chain[i % L]] = c
    i += 1
    while chain[i % L] != c:
        pos[chain[i % L]] = None
        i += 1

loop = [c]
k = c
while nextnode[k] != c:
    k = nextnode[k]
    loop.append(k)
print(len(loop))
for l in loop:
    print(l+1)

Submission status: Runtime Error

Solution code:
from collections import deque


n, m = map(int, input().split())
edges = [set() for _ in range(n)]
r_edges = [set() for _ in range(n)]
out_deg = [0]*n

for _ in range(m):
    a, b = map(int, input().split())
    edges[a-1].add(b-1)
    r_edges[b-1].add(a-1)
    out_deg[a-1] += 1

out_deg_node = sorted(range(len(out_deg)), key=lambda k: out_deg[k])
ng_node = set()

for node in out_deg_node:
    if out_deg[node] == 0:
        for rev in r_edges[node]:
            out_deg[rev] -= 1

        ng_node.add(node)
        edges[node] = []

    else:
        break

for i in range(n):
    edges[i] -= ng_node


def bfs(node):
    seen = [0] * n
    todo = deque([])
    for to in edges[node]:
        todo.append([to, 1, {to}])

    while todo:
        now, distance, path = todo.popleft()
        seen[now] = distance
        if now == node:
            return distance, path

        for next_node in edges[now]:  # type: int
            if seen[next_node] != 0:
                continue
            new_path = path | {next_node}
            todo.append([next_node, distance + 1, new_path])

    return float('INF'), set()


cycle_size = [float('INF')] * n
cycle_nodes = [set()] * n

for i in range(n):
    if i in ng_node:
        continue
    cycle_size[i], cycle_nodes[i] = bfs(i)

mini_cycle = min(cycle_size)
if mini_cycle == float('INF'):
    print(-1)
else:
    idx = cycle_size.index(mini_cycle)
    ans = cycle_nodes[idx]
    print(mini_cycle)
    for node in ans:
        print(node+1)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
data=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    data[a].append(b)
lst=[]
for i in range(1,n+1):
    h=[str(i)]
    while h:
        H=[]
        for u in h:
            a=int(u[-1])
            for v in data[a]:
                if v==i:
                    lst.append(int(u))
                    break
                else:
                    H.append(u.join(str(v)))
            else:
                continue
            break
        else:
            h=H
            continue
        break
print(lst)
lst.sort()
li=[]
flag=[0]*(n+1)
for u in lst:
    u=list(str(u))
    for v in u:
        if flag[int(v)]==1:
            break
    else:
        for v in u:
            flag[int(v)]=1
        li.append(u)
print(li)
for u in li:
    a=int(u[0])
    que=[a]
    while h:
        H=[]
        for i in que:
            if i==a:
                break
            H+=data[i]
        else:
            h=H
            continue
        break
    for i in u:
        if i in h:
            break
    else:
        print(len(u))
        for i in u:
            print(i)
        break
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
#N : 頂点　M : 辺
G  = [[] for _ in range(N)]

for i in range(M):
    a,b = map(int, input().split())
    G[a-1].append(b)

def dfs(v,goal,first = True):

    route.append(v)
    if not first:
        visit[v-1]=1        
        if v==goal:
            route.pop()
            return True

    for next in G[v-1]:
       
        if visit[next-1]:
            continue
        
        if dfs(next,goal,False) == True:
            return True
    route.pop()
    return False

flag = False

for nn in range(N):
    route = []
    visit = [0]*N
    flag = dfs(nn+1, nn+1)
    if flag:
        break

if flag:
    print(len(route))
    for i in route:
        print(i)
else:
    print(-1)