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: Wrong Answer

Solution code:
from collections import defaultdict, deque
import sys
sys.setrecursionlimit(20000000)

v, n = map(int, input().split())
es = [[int(x) for x in input().split()] for _ in range(n)]

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)

def dfs(n, l):
    global outs
    for out in outs[n]:
        if out in l:
            if len(l) < v:
                print(len(l))
                for i in l:
                    print(i)
                exit()
        else:
            dfs(out, l[:] + [out])


if len(res) == v+1:
    print("-1")
else:
    for i in range(1, v+1):
        dfs(i, [])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
if not m:
    print(-1)
    exit()
e=[[]for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    e[a-1]+=b-1,
f=[None]*n
f[0]=-1
s=[0]
while s:
    v=s.pop()
    for w in e[v]:
        if f[w]!=None:
            ans=[]
            while v!=w:
                if len(ans)>n or v==None:
                    print(-1)
                    exit()
                ans+=v+1,
                v=f[v]
            ans+=w+1,
            if len(ans)<3:
                print(-1)
            else:
                print(len(ans))
                print(*ans[::-1],sep='\n')
            exit()
        else:
            f[w]=v
            s+=w,
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

n, m = list(map(int, input().split()))

edges = [[] for _ in range(n + 1)]
for _ in range(m):
	frm, to = list(map(int, input().split()))
	edges[frm].append(to)

def dfs(cur, visited, do_not_visit, es):
	#print(cur, visited, do_not_visit)
	if len(visited) > 0 and cur == visited[0] and len(set(es) & set(do_not_visit)) == 1:
		print(len(visited))
		for x in visited:
			print(x)
		sys.exit()
	if len(edges[cur]) == 0:
		return
	else:
		for e in edges[cur]:
			if e not in do_not_visit:
				dfs(e, visited + [cur], do_not_visit + edges[cur], edges[cur])

for i in range(1, n + 1):
	dfs(i, [], [], edges[i])

print(-1)

Submission status: Wrong Answer

Solution code:
print("4\n2\n3\n4\n5")

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

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

AB = []
lis = [ [] for i in range(N)]

for i in range(M):

    A,B = map(int,input().split())

    A -= 1
    B -= 1

    lis[A].append(B)

q = deque([])

first = [-1] * (N+1)
first[0] = 0
first[-1] = 0

q.append( first )

while len(q) > 0:

    now = q.pop()
    lasp = now[-1]
    nownum = now[lasp]

    #print (q,now,lasp,nownum)

    for nex in lis[lasp]:

        if now[nex] == -1:
            ncopy = now.copy()
            ncopy[nex] = nownum + 1
            ncopy[-1] = nex
            q.append(ncopy)

        else:

            flag = True

            for i in range(N):

                if now[i] >= 0:

                    for j in lis[i]:

                        if (now[j] >= now[nex] and now[j] != now[i] + 1) and not (i == lasp and j == nex):
                            flag = False
                            break

                if not flag:
                    break

            if flag:
                ans = []

                for i in range(N):
                    if now[i] >= now[nex]:
                        ans.append(i + 1)

                print (len(ans))
                for i in ans:
                    print (i)

                sys.exit()

            #print (flag,nex,lasp)

print (-1)

Submission status: Wrong Answer

Solution code:
print("3\n1\n2\n4\n")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

from copy import copy

n,m = map(int, input().split())

G = [[] for i in range(n)]

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

def dfs(cur, s, start):
    if cur == start and len(s) != 0:
        print(len(s))
        for i in s:
            print(i+1)
        exit()
    s.add(cur)
    a = []
    cnt = 0
    f = False
    for to in G[cur]:
        if to in s:
            cnt += 1
            if to == start:
                f = True
        if cnt > 1 or cnt==1 and not f:
            return
        a.append(to)
    if f:
        dfs(start, s, start)
    for to in a:
        ss = copy(s)
        dfs(to, ss, start)

for i in range(n):
    dfs(i, set(), i)
print(-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
neighbours = [[] for i in range(N)]
for i in range(M):
    A, B = map(lambda x:int(x)-1,input().split())
    neighbours[A].append(B)
print()
visited = [False for i in range(N)]
parents = [None for i in range(N)]

def bfs(node):
    stack = [node]
    while stack:
        item = stack.pop(0)
        orig = item
        for neighbour in neighbours[item]:
            if visited[neighbour]:
                try:
                    graph = {neighbour}
                    while item != neighbour:
                        graph.add(item)
                        item = parents[item]
                        if item == orig and item != neighbour:
                            1/0
                    print(len(graph))
                    for item in graph:
                        print(item+1)
                    return True
                except:
                    pass
            if not visited[neighbour]:
                parents[neighbour] = item
                visited[neighbour] = True
                stack.append(neighbour)
            
for i in range(N):
    if not visited[i]:
        if bfs(i):
            break
else:
   print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

n, m = list(map(int, input().split()))

edges = [[] for _ in range(n + 1)]
for _ in range(m):
	frm, to = list(map(int, input().split()))
	edges[frm].append(to)

def dfs(cur, visited, do_not_visit):
	#print(cur)
	if len(visited) > 0 and cur == visited[0]:
		print(len(visited))
		for x in visited:
			print(x)
		sys.exit()
	if len(edges[cur]) == 0:
		return
	else:
		if len(set(edges[cur]) & set(do_not_visit)) > 0:
			return
		for e in edges[cur]:
			if e not in do_not_visit:
				dfs(e, visited + [cur], do_not_visit + edges[cur])

for i in range(1, n + 1):
	dfs(i, [], [])

print(-1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
Eb = [{} for _ in [0]*N]
for a,b in AB:
    E[a-1][b-1] = 1
    Eb[b-1][a-1] = 1

import heapq
def Dijkstra(N,E,start):
    d = [-1]*N
    q = [(0,start)]
    while q:
        ci,i = heapq.heappop(q)
        if d[i]!= -1:continue
        d[i] = ci
        for j,cj in E[i].items():
            if d[j]!=-1:continue
            heapq.heappush(q,(ci+cj,j))
    return d

ans = False
for i in range(N):
    d = Dijkstra(N,E,i)
    for j in Eb[i]:
        if d[j] >0:
            ans = [d[j]+1]
            while j!=i:
                ans.append(j+1)
                dj = d[j]
                for k in Eb[j]:
                    if d[k] == dj-1:
                        j = k
                        break
            ans.append(i+1)
            break
    if ans : break
else:
    ans = [-1]
for out in ans:
    print(out)

Submission status: Wrong Answer

Solution code:
import collections
V, E = [int(_) for _ in input().split()]
G = [set() for _ in range(V + 1)]
G2 = [set() for _ in range(V + 1)]

cand1 = set()
cand2 = set()

for _ in range(E):
    s, t = [int(_) for _ in input().split()]
    G2[s].add(t)
    cand1.add(s)
    cand2.add(t)
cand = cand1 & cand2
for s in range(V + 1):
    for t in G2[s]:
        if s in cand and t in cand:
            G[s].add(t)
seen = [False] * (V + 1)


def bellman_ford(V, G, i):
    INF = float('inf')
    DP = [[INF, -1]] * (V + 1)
    DP[i][0] = 0
    for _ in range(V):
        update = False
        for s in range(1, V + 1):
            for t in G[s]:
                if DP[s][0] != INF and DP[t][0] > DP[s][0] - 1:
                    seen[t] = True
                    DP[t] = [DP[s][0] - 1, s]
                    update = s
        if not update:
            return
    now = update
    ans = []
    while len(ans) == 0 or now != update:
        ans += [now]
        now = DP[now][1]
    print(len(ans))
    print(*ans[::-1], sep='\n')
    exit()


for i in cand:
    if not seen[i]:
        seen[i] = True
        bellman_ford(V, G, i)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def dfs(graph, cur, target, visited, memo=[]):
    for nex in graph[cur]:
        if not visited[nex]:
            visited[nex] = True
            ret = dfs(graph, nex, target, visited, memo)
            if ret != -1:
                memo.append(cur)
                return cur

            elif nex == target:
                memo.append(cur)
                return cur

    return -1



n, m = li()
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = li_()
    graph[a].append(b)

for target in range(n):
    visited = [False]*n
    memo = []
    ans = dfs(graph, target, target, visited, memo)
    if len(memo) > 0:
        break

if ans == -1:
    print(-1)
else:
    print(len(memo))
    while memo:
        print(memo.pop() + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

a,b=map(int,input().split())
c=[[] for i in range(a)]
for i in range(b):
  x,y=map(int,input().split())
  c[x-1].append(y-1)
  
d=deque()
ans=-1
e=[-1 for i in range(a)]
for i in range(a):
  f=[0 for i in range(a)]
  if e[i]==-1:
    d.append(i)
    while len(d)!=0:
      x=d.pop()
      for y in c[x]:
        e[y]=x
        if f[y]==1:
          ans= y
          break
        else:
          f[y]=1
          d.append(y)
      if ans>-1:
        break
    if ans>-1:
      break
        
  if i==a-1:
    print(-1)
    break
y=ans    
ans2=[]
while 1:
  ans2.append(e[y]+1)
  y=e[y]
  if y==ans:
    break
    
print(len(ans2))
for i in (ans2):
  print(i)

Submission status: Wrong Answer

Solution code:
import collections
V, E = [int(_) for _ in input().split()]
G = collections.defaultdict(set)

for _ in range(E):
    s, t = [int(_) for _ in input().split()]
    G[s].add(t)

seen = [False] * (V + 1)


def bellman_ford(V, G, i):
    INF = float('inf')
    DP = [[INF, -1]] * (V + 1)
    DP[i][0] = 0
    for cycle in range(V):
        update = False
        for s in G:
            for t in G[s]:
                if DP[s][0] != INF and DP[t][0] > DP[s][0] - 1:
                    seen[t] = True
                    DP[t] = [DP[s][0] - 1, s]
                    update = s
        if not update:
            return
        if cycle == V - 1:
            now = update
            ans = []
            while len(ans) == 0 or now != update:
                ans += [now]
                now = DP[now][1]
            print(len(ans))
            print(*ans[::-1], sep='\n')
            exit()


for i in range(1, V + 1):
    if not seen[i]:
        seen[i] = True
        bellman_ford(V, G, i)
print(-1)

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
ab = {}
for _ in range(m):
    a, b = [int(i)-1 for i in input().split()]
    if a in ab:
        ab[a].append(b)
    else:
        ab[a] = [b]

for i in range(n):
    c = [[] for _ in range(n)]
    c[i]=[i]
    for _ in range(n):
        for j in ab:
            if c[j] != []:
                for k in ab[j]:
                    if k == i:
                        print(len(c[j]))
                        for l in c[j]:
                            print(l + 1)
                        exit()
                    if c[k] == []:
                        c[k] = c[j] + [k]
print(-1)

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
ab = {}
for _ in range(m):
    a, b = [int(i)-1 for i in input().split()]
    if a in ab:
        ab[a].append(b)
    else:
        ab[a] = [b]

for i in range(n):
    c = [[] for _ in range(n)]
    c[i]=[i]
    for _ in range(n):
        for j in ab:
            if c[j] != []:
                for k in ab[j]:
                    if k == i:
                        for l in c[j]:
                            print(l + 1)
                        exit()
                    if c[k] == []:
                        c[k] = c[j] + [k]
print(-1)

Submission status: Wrong Answer

Solution code:
print(4)
print(2)
print(3)
print(4)
print(5)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque

N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
g = [[] for _ in range(N)]
for a, b in AB:
    g[a-1].append(b-1)

q = deque([(i, {i}) for i in range(N)])
min_loop = (math.inf, [])
while len(q) > 0:
    node, path = q.pop()
    for to_node in g[node]:
        if to_node in path:
            if min_loop[0] > len(path):
                min_loop = (len(path), path)
        else:
            q.append((to_node, path | {to_node}))
if min_loop[0] == math.inf:
    print(-1)
else:
    print(min_loop[0])
    for node in min_loop[1]:
        print(node+1)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque

N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
g = [[] for _ in range(N)]
for a, b in AB:
    g[a-1].append(b-1)

q = deque([(i, [i]) for i in range(N)])
min_loop = (math.inf, [])
while len(q) > 0:
    node, path = q.pop()
    for to_node in g[node]:
        if to_node in path:
            if min_loop[0] > len(path):
                min_loop = (len(path), path)
        else:
            q.append((to_node, path + [to_node]))
if min_loop[0] == math.inf:
    print(-1)
else:
    print(min_loop[0])
    for node in min_loop[1]:
        print(node+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    mi.discard(v)
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=start[0]
ans=[s+1]
nv=s
#print(seen,nv)
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)

print(len(ans))
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=start[0]
ans=[s+1]
nv=s
#print(seen,nv)
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)

print(len(ans))
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=start[0]
ans=[s+1]
#print(seen,nv)
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)

print(len(ans))
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=nv
ans=[s+1]
#print(seen,nv)
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)

print(len(ans))
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    for nv in g[v]:
        if seen[nv]!=-1:#閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
#print(seen,f)
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=nv
ans=[s+1]
#print(seen,nv)
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)
print(len(ans))
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  g[u].append(v)

from collections import deque
flg=False
seen=[-1]*n
mi=set(range(n))
s=0
while mi:
  s=mi.pop()
  root=[s]
  rootset={s}
  start=set(())
  todo=deque([[s,-1]])
  seen=[-1]*n
  while todo:
    v,p=todo.popleft()
    root.append(v)
    rootset.add(v)
    mi.discard(v)
    for nv in g[v]:
      if nv in rootset:
        start.add(nv)
        seen[nv]=v
        flg=True
      elif seen[nv]==-1:
        todo.append([nv,v])
        seen[nv]=v
    if flg:break
  if flg:break
if not flg:
  print(-1)
  exit()
ans=[v+1]
vv=seen[v]
ans.append(vv+1)
while vv not in start:
  vv=seen[vv]
  ans.append(vv+1)
#print(seen,s)
print(len(ans))
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
graph = {i:[] for i in range(N)}
for _ in range(M):
  a,b = IL()
  graph[a-1].append(b-1)
  
Q = [i for i in range(N)]
p = [None for i in range(N)]
heiro = []
while Q:
  deru = [False for i in range(N)]
  Flag = 0
  s = Q.pop()
  if p[s] != None: continue
  p[s] = -1
  q = deque([s])
  while q:
    flag = 0
    x = q.popleft()
    for y in graph[x]:
      deru[x] = True
      if not deru[y]:
        p[y] = x
        q.append(y)
      else:
        p[y] = x
        now = x
        while now != y:
          heiro.append(now)
          now = p[now]
        heiro.append(y)
        flag = 1
        break
    if flag:
      Flag = 1
      break
  if Flag:
    break

def graph_size(g):
  ret = 0
  for k in g:
    ret += len(g[k])
  return ret
def squeeze(l):
  check = [0 for i in range(N)]
  for i in l:
    check[i] = 1
  global graph
  edges = []
  subgraph = {k:[] for k in l}
  data = DD(lambda:DD(int))
  i = 0
  for k in l:
    for y in graph[k]:
      if check[y]:
        subgraph[k].append(y)
        edges.append([0,k,y])
        data[k][y] = i
        i += 1
  graph = subgraph
  s = l[0]
  i = data[p[s]][s]
  edges[i][0] = 1
  now = p[s]
  heiro = [s]
  while now != s:
    heiro.append(now)
    i = data[p[now]][now]
    edges[i][0] = 1
    now = p[now]
  if len(heiro)==len(edges):
    print(len(heiro))
    for x in heiro:
      print(x+1)
    exit()
  else:
    for b,k,y in edges:
      if not b:
        p[y] = k
        now = p[y]
        heiro = [y]
        while now != y:
          heiro.append(now)
          now = p[now]
        squeeze(heiro)

if not heiro:
  print(-1)
else:
  squeeze(heiro)