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

Solution (Python):
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
K=[0 for i in range(N)]
for i in range(N):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(N) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
if len(res)==N:
    print(-1)
    exit()
X={i for i in range(N)}
for st in range(N):
    before=[-1 for i in range(N)]
    q=deque([st])
    flag=0
    while(q):
        r=q.popleft()
        for p in G[r]:
            if before[p]==-1:
                before[p]=r
                q.append(p)
            if before[st]!=-1:
                Y={st}
                tmp=before[st]
                while(tmp!=st):
                    Y.add(tmp)
                    tmp=before[tmp]
                if len(Y)<len(X):
                    X={i for i in Y}
                flag=1
                break
        if flag:
            break
print(len(X))
for i in X:
    print(i+1)

Solution (Python):


import math
import os
import sys


sys.setrecursionlimit(1000000)


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, M, E):
    G = [set() for _ in range(N)]
    for a, b in E:
        G[a].add(b)

    visited = set()
    stk = []
    stki = {}

    def dfs(i):
        if i in visited:
            return

        stki[i] = len(stk)
        stk.append(i)

        for j in G[i]:
            if j in visited:
                continue
            if j in stki:
                si = stki[j]
                vset = set(stk[si:])
                loopd = {}
                for k in range(si, len(stk) - 1):
                    loopd[stk[k]] = stk[k + 1]
                loopd[stk[-1]] = stk[si]
                return slim_loop(vset, loopd)
            result = dfs(j)
            if result:
                return result

        stk.pop()
        del stki[i]
        visited.add(i)
        return None

    def slim_loop(vset, loopd):
        i = next(iter(vset))
        endi = i
        while True:
            jset = G[i] & vset
            if len(jset) > 1:
                oj = loopd[i]
                for j in jset:
                    if j == oj or j not in vset:
                        continue
                    k = loopd[i]
                    while k != j:
                        vset.remove(k)
                        k = loopd[k]
                    loopd[i] = j
                endi = i

            i = loopd[i]
            if i == endi:
                break

        return vset

    for i in range(N):
        if i not in visited:
            result = dfs(i)
            if result:
                return result

    return None


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

    result = solve(N, M, E)
    if not result:
        print('-1')
    else:
        print(len(result))
        for v in result:
            print(v + 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
N,M=map(int,input().split())
d=[set()for _ in range(N+1)]
def f(v,h,q):
 if d[v]&q:
  l,L=[],[]
  for x in h:
   l=[x]+l
   if x in d[v]:break
  while v!=x:
   for y in l:
    if v in d[y]:
     L,v=[v]+L,y
     break
  print("\n".join(str(x)for x in[len(L)+1,x]+L));sys.exit()
 for u in d[v]:f(u,[u]+h,q|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
v=0;exec("v+=1;f(v,[v],{v});"*N)
print(-1)

Solution (Python):
import sys
N,M=map(int,input().split())
d=[set()for _ in range(N+1)]
def f(v,h,q):
 if d[v]&q:
  l=[]
  for x in h:
   l=[x]+l
   if x in d[v]:break
  L=[]
  while v!=x:
   for y in l:
    if v in d[y]:
     L=[v]+L
     v=y
     break
  print("\n".join(str(x)for x in[len(L)+1,x]+L));sys.exit()
 for u in d[v]:f(u,[u]+h,q|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
v=0;exec("v+=1;f(v,[v],{v});"*N)
print(-1)

Solution (Python):
import sys
N,M=map(int,input().split())
d=[set()for _ in range(N+1)]
def f(v,h,q):
 if d[v]&q:
  l=[]
  for x in h[::-1]:
   l=[x]+l
   if x in d[v]:break
  L=[]
  while v!=x:
   for y in l:
    if v in d[y]:
     L=[v]+L
     v=y
     break
  print("\n".join(str(x)for x in[len(L)+1,x]+L[::-1]));sys.exit()
 for u in d[v]:f(u,h+[u],q|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
v=0;exec("v+=1;f(v,[v],{v});"*N)
print(-1)

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline

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

rflag = False
for s in range(N):
	pre = [-1]*N
	start = s
	queue = [start]
	while len(queue)>0:
		nq = []
		for i in queue:
			for j in neighbor[i]:
				if pre[j]==-1:
					pre[j] = i
					nq.append(j)
					if j==start:
						rflag = True
						break
				
				
				
				

			if rflag: break
		if rflag: break
		queue = nq
	if rflag: break

if not rflag:
	print(-1)
else:
	v = [0]*N
	v[j] = 1
	roop = [j]
	i = j
	while pre[i]!=j:
		pret = pre[i]
		roop.append(pret)
		v[pret] = 1
		i = pret
	roop = roop+[j]
	roop = roop[::-1]

	update = True
	while update:
		update = False
		for i,vi in enumerate(roop):
			if i==len(roop)-1: break
			for ni in neighbor[vi]:
				if ni!=roop[i+1] and v[ni]==1:
					pre[ni] = vi

					v = [0]*N
					v[ni] = 1
					roopn = [ni]
					j = ni
					while pre[j]!=ni:
						pret = pre[j]
						roopn.append(pret)
						v[pret] = 1
						j = pret
					roopn = roopn+[ni]
					update = True
					roop = roopn[::-1]
					break

			if update: break

	K = len(roop)-1
	print(K)
	print(*map(lambda x:x+1,roop[:-1]), sep='\n')

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def find_cycle(graph, vst):
    que = deque([vst])
    dist = [-1] * n
    pre = [-1] * n
    dist[vst] = 0
    flag = False
    while que:
        cur = que.popleft()
        for nxt in graph[cur]:
        
            if nxt == vst:
                flag = True
                break
            if dist[nxt] != -1:
                continue
            pre[nxt] = cur
            dist[nxt] = dist[cur] + 1
            que += [nxt]
        if flag:
            v = cur
            cycle = []
            while v != -1:
                cycle += [v]
                v = pre[v]
            return cycle


ret_len = INF
n, m = LI()
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    graph[a - 1] += [b - 1]


min_cycle = 0
for vst in range(n):
    cycle = find_cycle(graph, vst)
    if cycle and len(cycle) < ret_len:
        min_cycle = cycle
        ret_len = len(cycle)


if min_cycle:
    print(ret_len)
    for i in min_cycle:
        print(i + 1)
else:
    print(-1)

Solution (Python):
N,M=map(int, input().split())
vs=set()
def dfs(v,path,pvs):
    lp=l=N+1
    for u in d[v]:
        if u in pvs:
            for i, c in enumerate(path):
                if c == u:
                    break
            nlp = path[i+1:]+[u]
            nl = len(nlp)
            if nl < l:
                lp, l = nlp, nl
        if u in vs:
            continue
        vs.add(u)
        nl, nlp = dfs(u,path+[u],pvs|{u})
        if nl < l:
            lp, l = nlp, nl
    return l,lp
d = [set() for _ in range(N+1)]
for _ in range(M):
    a,b=map(int,input().split())
    d[a].add(b)
for i in range(N):
    v=i+1
    l,lp=dfs(i+1,[v],{v})
    if l<=N:
        print("\n".join(str(x) for x in[l]+lp))
        break
else:
    print(-1)

Solution (Python):
N, M = [int(x) for x in input().strip().split(" ")]
vs=set()

def dfs(v, path):
    lp = 0
    l = N+1
    for u in d[v]:
        if u in pvs:
            for i, c in enumerate(path):
                if c == u:
                    break
            nlp = path[i+1:]+[u]
            nl = len(nlp)
            if nl < l:
                lp, l = nlp, nl
        if u in vs:
            continue
        pvs.add(u)
        vs.add(u)
        nl, nlp = dfs(u,path+[u])
        if nl < l:
            lp, l = nlp, nl
        pvs.remove(u)
    return l, lp

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = map(int,input().split(" "))
    d[a].add(b)
for i in range(N):
    v=i+1
    pvs = set([v])
    l, lp = dfs(i+1, [v])
    if l != N+1:
        print(l)
        for l in lp:
            print(l)
        break
else:
    print(-1)

Solution (Python):
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N + 1)]

for a, b in AB:
    graph[a].append(b)


def cycle_size(from_v):
    """
    from_v に戻ってくるまでのステップ数
    :param from_v:
    :return:
    """
    parents = [None] * len(graph)
    seen = [False] * len(graph)
    que = deque([(from_v, 0)])
    while que:
        v, d = que.pop()
        for u in graph[v]:
            if seen[u]:
                continue
            seen[u] = True
            que.appendleft((u, d + 1))
            parents[u] = v
            if u == from_v:
                return d + 1, parents
    return INF, parents


min_v = None
min_size = INF
min_parents = None
for v in range(1, N + 1):
    size, parents = cycle_size(v)
    if size < min_size:
        min_v = v
        min_size = size
        min_parents = parents

if min_size < INF:
    print(min_size)
    print(min_v)
    v = min_parents[min_v]
    while v != min_v:
        print(v)
        v = min_parents[v]
else:
    print(-1)

Solution (Python):
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N + 1)]

for a, b in AB:
    graph[a].append(b)


def cycle_size(from_v):
    """

    :param from_v:
    :return:
    """
    parents = [None] * len(graph)
    seen = [False] * len(graph)
    que = deque([(from_v, 0)])
    while que:
        v, d = que.pop()
        for u in graph[v]:
            if seen[u]:
                continue
            seen[u] = True
            que.appendleft((u, d + 1))
            parents[u] = v
            if u == from_v:
                return d + 1, parents
    return INF, parents


min_v = None
min_size = INF
min_parents = None
for v in range(1, N + 1):
    size, parents = cycle_size(v)
    if size < min_size:
        min_v = v
        min_size = size
        min_parents = parents

if min_size < INF:
    print(min_size)
    print(min_v)
    v = min_parents[min_v]
    while v != min_v:
        print(v)
        v = min_parents[v]
else:
    print(-1)

Solution (Python):
import sys
from collections import deque
N, M = map(int, input().split())
edges = [[] for i in range(N)]
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    AB.append((a-1, b-1))
def BFS(s):
    prev = [-1]*N
    que = deque([s])
    while que:
        v = que.pop()
        for nv in edges[v]:
            if nv == s:
                prev[nv] = v
                return (s, prev)
            if prev[nv]<0:
                que.append(nv)
                prev[nv] = v
    return (-1, prev)
for v in range(N):
    v0, prev = BFS(v)
    if v0>=0:
        break
if v0<0:
    print(-1)
    sys.exit()
circle = set()
circle.add(v0)
pv = prev[v0]
while pv != v0:
    circle.add(pv)
    pv = prev[pv]
for a, b in AB:
    if a in circle and b in circle and prev[b] != a:
        pv = prev[b]
        while pv != a:
            circle.remove(pv)
            pv = prev[pv]
        prev[b] = a
print(len(circle))
for i in circle:
    print(i+1)

Solution (Python):
N, M = [int(x) for x in input().strip().split(" ")]

def dfs(v):
    pvs = set([v])
    path = [v]
    def _dfs(v, path):
        for u in d[v]:
            if u in pvs:
                for i, c in enumerate(path):
                    if c == u:
                        break
                return path[i+1:]  + [u]
            if u in vs:
                continue
            pvs.add(u)
            vs.add(u)
            loop = _dfs(u, path + [u])
            pvs.remove(u)
            if loop:
                return loop
        return False
    return _dfs(v, path)

vs = set()
def dfs_w(v, d):
    
    pvs = set([])
    stack = [v]
    path = []
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v < 0:
            pvs.remove(path[-1])
            path.pop()
        else:
            path.append(v)
            pvs.add(v)
            vs.add(v)
            for u in d[v]:
                if u in pvs:
                    for i, c in enumerate(path):
                        if c == u:
                            break
                    return path[i+1:]  + [u]
                if u in vs:
                    continue
                stack += [-v, u]
    return False

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(b)

for i in range(N):
    i += 1
    if i in vs:
        continue
    loop = dfs_w(i, d)
    if loop:
        break

if not loop:
    print(-1)
    import sys
    sys.exit()

v2i = [-1 for _ in range(N+1)]
for i, v in enumerate(loop):
    v2i[v] = i

nloop, pvs = [], set()
v = loop[0]
f = False
while True:
    nloop.append(v)
    pvs.add(v)
    max_i = max_i_l = -1
    for u in d[v]:
        if v2i[u] == -1:
            continue
        if v2i[v] > v2i[u] and u in pvs:
            f = True
            max_i_l = max(max_i_l, v2i[u])
        if v2i[u] > v2i[v]:
            max_i = max(max_i, v2i[u])
    if f:
        nloop.append(loop[max_i_l])
        break
    v = loop[max_i]

for i, x in enumerate(nloop):
    if x == nloop[-1]:
        break
nloop = nloop[i+1:]
print(len(nloop))
for v in nloop:
    print(v)

Solution (Python):
N, M = [int(x) for x in input().strip().split(" ")]

def dfs(v):
    pvs = set([v])
    path = [v]
    def _dfs(v, path):
        for u in d[v]:
            if u in pvs:
                for i, c in enumerate(path):
                    if c == u:
                        break
                return path[i+1:]  + [u]
            if u in vs:
                continue
            pvs.add(u)
            vs.add(u)
            loop = _dfs(u, path + [u])
            pvs.remove(u)
            if loop:
                return loop
        return False
    return _dfs(v, path)

vs = set()
def dfs_w(v, d):
    
    pvs = set([])
    stack = [v]
    path = []
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v < 0:
            pvs.remove(path[-1])
            path.pop()
        else:
            path.append(v)
            pvs.add(v)
            vs.add(v)
            for u in d[v]:
                if u in pvs:
                    for i, c in enumerate(path):
                        if c == u:
                            break
                    return path[i+1:]  + [u]
                if u in vs:
                    continue
                stack += [-v, u]
    return False

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(b)

for i in range(N):
    i += 1
    if i in vs:
        continue
    loop = dfs_w(i, d)
    if loop:
        break

if not loop:
    print(-1)
    import sys
    sys.exit()

v2i = [-1 for _ in range(N+1)]
for i, v in enumerate(loop):
    v2i[v] = i

nloop, pvs = [], set()
v = loop[0]
f = False
while True:
    nloop.append(v)
    pvs.add(v)
    max_i = max_i_l = -1
    for u in d[v]:
        if v2i[u] == -1:
            continue
        if v2i[v] > v2i[u] and u in pvs:
            f = True
            max_i_l = max(max_i_l, v2i[u])
        if v2i[u] > v2i[v]:
            max_i = max(max_i, v2i[u])
    if f:
        nloop.append(loop[max_i_l])
        break
    v = loop[max_i]

for i, x in enumerate(nloop):
    if x == nloop[-1]:
        break
nloop = nloop[i+1:]
print(len(nloop))
for v in nloop:
    print(v)

Solution (Python):
from collections import deque


def shortest_cycle_path(graph, start):
    """重み無し有向グラフgraphに対して、startから出発してstartに帰るサイクルの最短経路を求める
    サイクルが存在しないときは空のリスト [] を返す
    例) start = 0 のときの最短サイクルが 0 -> 3 -> 1 -> 0 のとき、
        [0, 3, 1, 0] を返す
    """
    n = len(graph)
    dist = [-1] * n
    prev_pos = [-1] * n
    q = deque([start])
    dist[start] = 0
    while q:
        pos = q.pop()
        for next_pos in graph[pos]:
            if dist[next_pos] == -1:
                dist[next_pos] += dist[pos] + 1
                prev_pos[next_pos] = pos
                q.append(next_pos)

    
    
    path = []
    path_len = 10**9 + 7
    for goal in range(n):
        if start == goal or dist[goal] == -1:
            continue
        for next_pos in graph[goal]:
            
            if next_pos == start:
                tmp_path = []
                pos = goal
                while True:
                    tmp_path.append(pos)
                    if pos == start:
                        break
                    pos = prev_pos[pos]
                if len(tmp_path) < path_len:
                    path_len = len(tmp_path)
                    path = [start] + tmp_path[0:]
    path = path[::-1]
    return path


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

len_ans = 10**9 + 7
ans = []
for i in range(n):
    tmp = shortest_cycle_path(graph, i)
    if len(tmp) != 0 and len(tmp) < len_ans:
        len_ans = len(tmp)
        ans = tmp
if ans:
    print(len(ans) - 1)
    for i in range(len(ans) - 1):
        print(ans[i] + 1)
else:
    print(-1)

Solution (Python):
N, M = [int(x) for x in input().strip().split(" ")]

def dfs(v):
    pvs = set([v])
    path = [v]
    def _dfs(v, path):
        for u in d[v]:
            if u in pvs:
                for i, c in enumerate(path):
                    if c == u:
                        break
                return path[i+1:]  + [u]
            if u in vs:
                continue
            pvs.add(u)
            vs.add(u)
            loop = _dfs(u, path + [u])
            pvs.remove(u)
            if loop:
                return loop
        return False
    return _dfs(v, path)

def dfs_w(v):
    
    pvs = set([])
    nvs = [v]
    path = []
    while True:
        if len(nvs) == 0:
            break
        v = nvs.pop()
        if v < 0:
            pvs.remove(path[-1])
            path.pop()
        else:
            path.append(v)
            pvs.add(v)
            vs.add(v)
            for u in d[v]:
                if u in pvs:
                    for i, c in enumerate(path):
                        if c == u:
                            break
                    return path[i+1:]  + [u]
                if u in vs:
                    continue
                nvs += [-v, u]
    return False

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(b)

vs = set()
for i in range(N):
    i += 1
    if i in vs:
        continue
    vs.add(i)
    loop = dfs_w(i)

    if loop:
        break

if not loop:
    print(-1)
    import sys
    sys.exit()

v2i = [-1 for _ in range(N+1)]
for i, v in enumerate(loop):
    v2i[v] = i

nloop, pvs = [], set()
v = loop[0]
f = False
while True:
    nloop.append(v)
    pvs.add(v)
    max_i = max_i_l = -1
    for u in d[v]:
        if v2i[u] == -1:
            continue
        if v2i[v] > v2i[u] and u in pvs:
            f = True
            max_i_l = max(max_i_l, v2i[u])
        if v2i[u] > v2i[v]:
            max_i = max(max_i, v2i[u])
    if f:
        if max_i_l < 0:
            1/0
        nloop.append(loop[max_i_l])
        break
    if max_i < 0:
        1/0
    v = loop[max_i]

for i, x in enumerate(nloop):
    if x == nloop[-1]:
        break
nloop = nloop[i+1:]
print(len(nloop))
for v in nloop:
    print(v)

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def bfs(u):
        dist = [inf] * n
        cur = [u]
        pre = [-1] * n
        dist[u] = 0
        d = 0
        while cur:
            d += 1
            nxt = []
            for v in cur:
                for kv in to[v]:
                    if dist[kv] != inf: continue
                    dist[kv] = d
                    pre[kv] = v
                    nxt.append(kv)
            cur = nxt
        mn = [inf, -1]
        for v in range(n):
            if v == u: continue
            if u in to[v]:
                mn = min(mn, [dist[v], v])

        
        
        
        res = []
        v = mn[1]
        if mn[0] == inf:
            return [0] * (n + 1)
        for _ in range(mn[0] + 1):
            res.append(v)
            v = pre[v]
        return res

    inf = 10 ** 9
    n, m = map(int, input().split())
    to = defaultdict(set)
    for _ in range(m):
        u, v = map(int, input().split())
        to[u - 1].add(v - 1)
    ans = [0] * (n + 1)
    for u in range(n):
        res = bfs(u)
        if len(res) < len(ans):
            ans = res
    if len(ans) == n + 1:
        print(-1)
    else:
        print(len(ans))
        for u in ans:
            print(u + 1)

main()

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

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

dist = [[-1] * n for _ in range(n)]
for i in range(n):
    queue = deque([(i, 0)])
    while queue:
        v, c = queue.popleft()
        for v_next in graph[v]:
            if dist[i][v_next] == -1:
                dist[i][v_next] = c + 1
                queue.append((v_next, c+1))


ans_len = n + 1
for i in range(n):
    if dist[i][i] != -1:
        ans_len = min(ans_len, dist[i][i])
if ans_len == n + 1:
    print(-1)
else:
    for i in range(n):
        if dist[i][i] == ans_len:
            start_v = i
            break

    dist = [-1] * n
    prev_v = [-1] * n
    queue = deque([(start_v, 0)])
    while queue:
        v, c = queue.popleft()
        if v == start_v and c != 0:
            break
        for v_next in graph[v]:
            if dist[v_next] == -1:
                dist[v_next] = c + 1
                prev_v[v_next] = v
                queue.append((v_next, c+1))

    ans = []
    
    
    
    v = start_v
    for i in range(ans_len):
        ans.append(v+1)
        v = prev_v[v]

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

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

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

dist = [[-1] * n for _ in range(n)]
for i in range(n):
    queue = deque([(i, 0)])
    while queue:
        v, c = queue.popleft()
        for v_next in graph[v]:
            if dist[i][v_next] == -1:
                dist[i][v_next] = c + 1
                queue.append((v_next, c+1))


ans_len = n + 1
for i in range(n):
    if dist[i][i] != -1:
        ans_len = min(ans_len, dist[i][i])
if ans_len == n + 1:
    print(-1)
else:
    for i in range(n):
        if dist[i][i] == ans_len:
            start_v = i
            break

    dist = [-1] * n
    prev_v = [-1] * n
    queue = deque([(start_v, 0)])
    while queue:
        v, c = queue.popleft()
        if v == start_v and c != 0:
            break
        for v_next in graph[v]:
            if dist[v_next] == -1:
                dist[v_next] = c + 1
                prev_v[v_next] = v
                queue.append((v_next, c+1))

    ans = []
    
    
    
    v = start_v
    for i in range(ans_len):
        ans.append(v+1)
        v = prev_v[v]

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

Solution (Python):
import sys
import math
from collections import defaultdict

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

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



def shortest_path(pt,s,t):
    n = len(pt)
    used = [False]*n
    pre = [-1]*n
    q = [s]
    while q:
        q1 = []
        for i in q:
            for j in pt[i]:
                if not used[j]:
                    used[j] = True
                    pre[j] = i
                    q1.append(j)
        q = q1

    if used[t]:
        path = [t]
        p = t
        while True:
            p = pre[p]
            path.append(p)
            if p == s:
                break
        return list(reversed(path))
    else:
        return []

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

N,M = II()
A,B = Line(M,2)

use_path = []
pt = edges_to_pt(A,B,N,True)
l = N+1
for i in range(N):
    s = shortest_path(pt,i,i)
    if s:
        s.pop()
        if len(s)<l:
            use_path = s
            l = len(s)

if use_path:
    print(len(use_path))
    for v in use_path:
        print(v+1)
else:
    print(-1)

Solution (Python):

def find_cycle(g):
    n = len(g)
    used = [0]*n 
    for v in range(n): 
        if used[v] == 2: continue
        
        stack = [v]
        hist =[] 
        while stack:
            v = stack[-1]
            if used[v] == 1:
                used[v] = 2 
                stack.pop()
                hist.pop()
                continue
            hist.append(v)
            used[v] = 1 
            for c in g[v]:
                if used[c] == 2: continue
                elif used[c] == 1: 
                    return hist[hist.index(c):]
                else:
                    stack.append(c)
    return None

def find_minimal_cycle(g,cycle):
    n = len(g)
    is_in_cycle = [0]*n 
    nxt = [-1]*n 
    
    l = len(cycle)
    for i,c in enumerate(cycle):
        is_in_cycle[c] = 1
        nxt[c] = cycle[i+1-l]

    
    for v in cycle:
        if is_in_cycle[v]:
            for c in g[v]:
                if is_in_cycle[c] == 1: 
                    v0 = nxt[v] 
                    while v0 != c: 
                        is_in_cycle[v0] = 0 
                        v0 = nxt[v0] 
                    nxt[v] = c 
    
    
    i = is_in_cycle.index(1)
    v = nxt[i]
    hist = [i] 
    while v != i:
        hist.append(v)
        v = nxt[v]
    return hist
    
    







import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n,m = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
 
for _ in range(m):
    a,b = [int(i)-1 for i in readline().split()]
    g[a].append(b)

cycle = find_cycle(g)

if cycle == None: print(-1)
else:
    res = find_minimal_cycle(g,cycle)
    print(len(res))
    for i in res:
        print(i+1)