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, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)

shortest = N + 1
ans = []
for s in range(1, N + 1):
    D = [-1] * (N + 1)
    P = [-1] * (N + 1)

    D[s] = 0
    Q = deque([s])
    while Q:
        p = Q.popleft()
        for c in E[p]:
            if D[c] < 0:
                D[c] = D[p] + 1
                P[c] = p
                Q.append(c)

    for t in range(1, N + 1):
        if t == s or D[t] < 0:
            continue

        for v in E[t]:
            if v != s:
                continue

            T = [s]
            cur = t
            while cur != s:
                T.append(cur)
                cur = P[cur]

            if shortest > len(T):
                shortest = len(T)
                ans = T

if shortest == N + 1:
    print(-1)
else:
    print(len(ans))
    print("\n".join(map(str, ans)))

Solution (Python):
from collections import deque

N, M, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)

shortest = N + 1
ans = []
for s in range(1, N + 1):
    D = [-1] * (N + 1)
    P = [-1] * (N + 1)

    D[s] = 0
    Q = deque([s])
    while Q:
        p = Q.popleft()
        for c in E[p]:
            if D[c] < 0:
                D[c] = D[p] + 1
                P[c] = p
                Q.append(c)

    for t in range(1, N + 1):
        if t == s or D[t] < 0:
            continue

        for v in E[t]:
            if v != s:
                continue

            T = [s]
            cur = t
            while cur != s:
                T.append(cur)
                cur = P[cur]

            if shortest > len(T):
                shortest = len(T)
                ans = T

if shortest == N + 1:
    print(-1)
else:
    print(len(ans))
    print("\n".join(map(str, ans)))

Solution (Python):
import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
cand1=set()
cand2=set()
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  cand1.add(a)
  cand2.add(b)
cand=cand1&cand2
ans=-1
for i in range(1,n+1):
  if i not in cand:
    continue
  else:
    q=collections.deque()
    q.append((i,[i]))
    checked=[0]*(n+1)
    while len(q)!=0:
      v,chain=q.popleft()
      if v==i and len(chain)!=1:
        ans=chain[:-1]
      for u in g[v]:
        if u not in cand:
          continue
        elif checked[u]==0:
          checked[u]=1
          q.append((u,chain+[u]))
    cand.discard(i)
if ans==-1:
  print(ans)
else:
  print(len(ans))
  for v in ans:
    print(v)

Solution (Python):
N, M = map(int, input().split())
tree = dict(zip(range(1, N+1), [[] for i in range(N)]))
for i in range(M):
  a, b = map(int, input().split())
  tree[a].append(b)


is_visited = [False]*(N+1)
num_visited = 0
def find_cycle(d):
  global is_visited
  global num_visited
  cycle = []
  l = 1001
  while d:
    node = d[-1]
    if tree[node]:
      child = tree[node].pop()
      if not is_visited[child]:
        is_visited[child] = True
        num_visited += 1
      if child in cycle and node in cycle:
        idn = cycle.index(node)
        idc = cycle.index(child)
        cycle = cycle[:idn+1] + cycle[idc:]
        l = len(cycle)
      if child in d:
        idx = d.index(child)
        if len(d) - idx < l:
          cycle = d[idx:]
          l = len(cycle)
      else:
        d.append(child)
    else:
      d.pop()
  return cycle


is_visited[0] = True
num_visited += 1
i = 1
while num_visited < N+1:
  while is_visited[i]:
    i += 1
  d = [i]
  is_visited[i] = True
  num_visited += 1
  cycle = find_cycle(d)
  if cycle:
    print(len(cycle))
    print(*cycle, sep='\n')
    quit()

print(-1)

Solution (Python):
import sys

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)

needless = set(range(1, N + 1)) - A_s

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



def dfs(original_stack):
    checked = [False] * (N + 1)
    while original_stack:
        start = original_stack.pop()
        if checked[start]:
            continue
        checked[start] = True
        stack = [(start, [start])]
        while stack:
            v, route = stack.pop()
            for i in graph[v]:
                if i in route:
                    return route[route.index(i):]
                else:
                    stack.append((i, route + [i]))
                    checked[i] = True


v = dfs([i for i in range(1, N + 1) if graph[i]])
if not v:
    print(-1)
    exit()

while True:
    v_s = set(v)
    length = len(v)
    for i, (v_i, v_j) in enumerate(zip(v, v[1:] + [v[0]])):
        for j in graph[v_i]:
            if j != v_j and j in v_s:
                idx = v.index(j)
                if i < idx:
                    v = v[:i + 1] + v[idx:]
                else:
                    v = v[idx:i + 1]
                break
        else:
            continue
        break
    else:
        print(len(v))
        print('\n'.join(map(str, v)))
        exit()

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

from collections import deque
tmpdist = N
ans = None
for to in range(N):
    for fr in es[to]:
        dist = [N] * N
        dist[fr] = 0
        prev = [-1] * N
        q = deque([fr])
        while q:
            v = q.popleft()
            if v==to: break
            for w in es[v]:
                if dist[w] < N: continue
                if v==to and w==fr: continue
                dist[w] = dist[v] + 1
                prev[w] = v
                q.append(w)
        else:
            continue
        if dist[to] < tmpdist:
            tmpdist = dist[to]
            ans = set()
            v = to
            while 1:
                ans.add(v+1)
                if prev[v] < 0: break
                v = prev[v]
if ans is None:
    print(-1)
else:
    print(len(ans))
    print(*ans, sep='\n')

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

N, M = map(int, input().split())
adjL = [set() for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    adjL[A].add(B)

def getCycle(adjL):
    def dfs(vNow):
        if isAvails[vNow]:
            anss.append(vNow)
            return vNow
        useds[vNow] = True
        isAvails[vNow] = True
        for v2 in adjL[vNow]:
            vRet = dfs(v2)
            if vRet == vNow or vRet == numV:
                return numV
            elif vRet != -1:
                anss.append(vNow)
                return vRet
        isAvails[vNow] = False
        return -1

    numV = len(adjL)
    useds = [False] * numV
    anss = []
    for vSt in range(numV):
        isAvails = [False] * numV
        if useds[vSt]: continue
        vRet = dfs(vSt)
        if vRet == numV:
            return anss[::-1]
    return []

cycle = getCycle(adjL)

if not cycle:
    print(-1)
    sys.exit()

isAvails = [False] * N
v2s = [-1] * N
for i in range(len(cycle)):
    isAvails[cycle[i]] = True
    v2s[cycle[i-1]] = cycle[i]

while True:
    adjL2 = [set() for _ in range(N)]
    a, b = -1, -1
    for v in cycle:
        for v2 in adjL[v]:
            if isAvails[v2]:
                adjL2[v].add(v2)
                if v2s[v] != v2:
                    a, b = v, v2

    if (a, b) == (-1, -1):
        print(len(cycle))
        print('\n'.join(map(lambda x: str(x+1), cycle)))
        break

    adjL = adjL2

    cycle = []
    isAvails = [False] * N
    v2s[a] = b
    v = a
    while not isAvails[v]:
        cycle.append(v)
        isAvails[v] = True
        v = v2s[v]

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
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)
    
    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)

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

from collections import deque

d = N+1
flag = False
for i in range(N):
    for v in E[i]:
        q = deque()
        q.append(v)
        used = [N+1]*N
        used[v] = 1
        while q:
            temp = q.popleft()
            if used[temp] > d:
                break
            for u in E[temp]:
                if u == i and d > used[temp]+1:
                    d = used[temp]+1
                    memo = [temp, u]
                    q = deque()
                    flag = True
                    break
                elif u == i:
                    q = deque()
                    break
                if used[u] < N+1:
                    continue
                used[u] = used[temp]+1
                q.append(u)

import heapq
if flag:
    h = []
    dist = [N+1]*N
    dist[memo[1]] = 0
    for v in E[memo[1]]:
        heapq.heappush(h, (1, v))
    while True:
        temp = heapq.heappop(h)
        if dist[temp[1]] < N+1:
            continue
        dist[temp[1]] = temp[0]
        if temp[1] == memo[0]:
            break
        for v in E[temp[1]]:
            if dist[v] < N+1:
                continue
            heapq.heappush(h, (temp[0]+1, v))
    ans = [memo[0]]
    d = dist[memo[0]]-1
    prev = memo[0]
    while d >= 0:
        for i in range(N):
            if dist[i] == d and prev in E[i]:
                prev = i
                ans.append(i)
                d -= 1
                break
    print(len(ans))
    for i in ans:
        print(i+1)
else:
    print(-1)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def SCC(N, edges):
    """ 強連結成分分解 """

    nodes1 = [[] for i in range(N)]
    nodes2 = [[] for i in range(N)]
    for u, v in edges:
        nodes1[u].append(v)
        nodes2[v].append(u)

    T = []
    visited = [False] * N
    def rec1(cur):
        visited[cur] = True
        for nxt in nodes1[cur]:
            if not visited[nxt]:
                rec1(nxt)
        
        T.append(cur)

    
    for u in range(N):
        if not visited[u]:
            rec1(u)

    visited = [False] * N
    group = [0] * N
    grpcnt = 0
    def rec2(cur):
        group[cur] = grpcnt
        visited[cur] = True
        for nxt in nodes2[cur]:
            if not visited[nxt]:
                rec2(nxt)

    
    for u in reversed(T):
        if not visited[u]:
            rec2(u)
            grpcnt += 1
    return grpcnt, group

def bfs(N, nodes, src):
    """ BFS(一般グラフ、重みなし) """
    from collections import deque

    que = deque([(src, -1, 0)])
    dist = [()] * N
    mn = INF
    end = -1
    while que:
        u, prev, c = que.popleft()
        
        if group[u] != group[src]:
            continue
        if dist[u]:
            
            if u == src:
                if c < mn:
                    mn = c
                    end = prev
            continue
        dist[u] = (c, prev)
        for v in nodes[u]:
            que.append((v, u, c+1))
    
    return dist, mn, end

def get_route(s, t, res):
    """ s,t間の経路を取得 """
    prev = t
    StoT = [t]
    while prev != s:
        prev = res[prev][1]
        if prev == -1:
            return None
        StoT.append(prev)
    StoT = StoT[::-1]
    return StoT

N, M = MAP()
nodes = [[] for i in range(N)]
edges = []
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    edges.append((a, b))


grpcnt, group = SCC(N, edges)
ans = INF
for i in range(N):
    
    dist, mn, end = bfs(N, nodes, i)
    if mn < ans:
        ans = mn
        route = get_route(i, end, dist)
if ans != INF:
    print(ans)
    [print(u + 1) for u in route]
else:
    
    print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**4)
def input():
	return sys.stdin.readline()[:-1]

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

seen = [False for _ in range(n)]
visited = [False for _ in range(n)]
begin = -1
hist = []

def dfs(x):
	global begin, hist
	if begin >= 0:
		return
	seen[x] = True
	hist.append(x)
	for v in adj[x]:
		if visited[v]:
			continue
		if seen[v] == True and visited[v] == False:
			begin = v
			return
		dfs(v)
		if begin >= 0:
			return
	visited[x] = True
	hist.pop()
	return

for i in range(n):
	if begin < 0:
		dfs(i)
	if begin >= 0:
		break

if begin < 0:
	print(-1)
	sys.exit()
else:
	cycle = []
	included = [False for _ in range(n)]
	included[begin] = True
	while hist and hist[-1] != begin:
		cycle.append(hist[-1])
		included[hist[-1]] = True
		hist.pop()
	cycle.append(begin)
	hist.pop()

	while True:
		meets = True
		l = len(cycle)
		ind = [-1 for _ in range(n)]
		for i in range(l):
			ind[cycle[i]] = i
		for i in range(l):
			if meets == False:
				break
			for v in adj[cycle[(i+1)%l]]:
				if included[v] == True and v != cycle[i]:
					meets = False
					new_start_id, new_end_id = ind[v], (i+1)%l
					break

		if meets:
			print(len(cycle))
			print(*[c+1 for c in cycle], sep="\n")
			break
		else:
			new_cycle = []
			included = [False for _ in range(n)]
			cur = new_end_id
			while cur != new_start_id:
				new_cycle.append(cycle[cur])
				included[cycle[cur]] = True
				cur = (cur+1)%l
			new_cycle.append(cycle[new_start_id])
			cycle = new_cycle

Solution (Python):
import sys
sys.setrecursionlimit(10**4)
def input():
	return sys.stdin.readline()[:-1]

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

seen = [False for _ in range(n)]
visited = [False for _ in range(n)]
begin = -1
hist = []

def dfs(x):
	global begin, hist
	if begin >= 0:
		return
	seen[x] = True
	hist.append(x)
	for v in adj[x]:
		if visited[v]:
			continue
		if seen[v] == True and visited[v] == False:
			begin = v
			return
		dfs(v)
		if begin >= 0:
			return
	visited[x] = True
	hist.pop()
	return

for i in range(n):
	if begin < 0:
		dfs(i)
	if begin >= 0:
		break

if begin < 0:
	print(-1)
	sys.exit()
else:
	cycle = []
	included = [False for _ in range(n)]
	included[begin] = True
	while hist and hist[-1] != begin:
		cycle.append(hist[-1])
		included[hist[-1]] = True
		hist.pop()
	cycle.append(begin)
	hist.pop()

	while True:
		meets = True
		l = len(cycle)
		ind = [-1 for _ in range(n)]
		for i in range(l):
			ind[cycle[i]] = i
		for i in range(l):
			if meets == False:
				break
			for v in adj[cycle[(i+1)%l]]:
				if included[v] == True and v != cycle[i]:
					meets = False
					new_start_id, new_end_id = ind[v], (i+1)%l
					break

		if meets:
			print(len(cycle))
			print(*[c+1 for c in cycle], sep="\n")
			break
		else:
			new_cycle = []
			included = [False for _ in range(n)]
			cur = new_end_id
			while cur != new_start_id:
				new_cycle.append(cycle[cur])
				included[cycle[cur]] = True
				cur = (cur+1)%l
			new_cycle.append(cycle[new_start_id])
			cycle = new_cycle

Solution (Python):
from collections import deque

n,m = map(int,input().split())
g = [list() for _ in range(n+1)]
en = [0]*(n+1)
for _ in range(m):
  u,v = map(int,input().split())
  g[u].append(v)
  en[v] += 1
q = deque(i for i in range(1,n+1) if en[i] == 0)
done = list()
while q:
  v = q.popleft()
  for x in g[v]:
    en[x] -= 1
    if not en[x]:
      q.append(x)
  done.append(v)
print(-1 if len(done) == n else 0)

Solution (Python):
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq
sys.setrecursionlimit(100000)


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()

Solution (Python):
from sys import stdin
import sys

import collections
from functools import cmp_to_key
import heapq


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()

Solution (Python):
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):
    flag=[0]*(N+1)
    parent=[0]*(N+1)
    que=[i]
    while que:
        h=[]
        for u in que:
            for v in data[u]:
                if flag[v]==0:
                    flag[v]=1
                    parent[v]=u
                    h.append(v)
        que=h
    if parent[i]==0:
        continue
    lsls=[i]
    zzz=i
    while True:
        zzz=parent[zzz]
        if zzz==i:
            break
        lsls.append(zzz)
    lst.append(lsls)
inf=float("inf")
k=inf
ans=None
for u in lst:
    if k>len(u):
        ans=u
        k=len(u)
if k==inf:
    print(-1)
else:
    print(k)
    for v in ans:
        print(v)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)

    
    A=[None]*n
    for s in range(n):
        dist=[INF]*n
        dist[s]=0
        Q=deque([s])
        while(Q):
            v=Q.popleft()
            for nv in E[v]:
                if(dist[nv]!=INF): continue
                dist[nv]=dist[v]+1
                if(nv!=s): Q.append(nv)
            if(v==s): dist[v]=INF
        A[s]=dist

    d,v0=min((A[v][v],v) for v in range(n))
    if(d==INF):
        print(-1)
        return

    print(d)
    
    prev=[None]*n
    used=[0]*n
    used[0]=1
    Q=deque([v0])
    while(Q):
        flag=True
        v=Q.popleft()
        for nv in E[v]:
            if(nv==v0):
                flag=False
                break
            if(used[nv]): continue
            used[nv]=1
            prev[nv]=v
            Q.append(nv)
        if(not flag): break

    ans=[]
    while(v!=v0):
        ans.append(v)
        v=prev[v]

    ans.append(v0)
    print(*map(lambda x:x+1,ans[::-1]),sep='\n')
resolve()

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)
else:
    print(0)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10000)
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)

Solution (Python):
def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*m]
    g=[set() for _ in [0]*n]
    g2=[set() for _ in [0]*n]
    [g[a-1].add(b-1) for a,b in ab]
    [g2[b-1].add(a-1) for a,b in ab]

    def bfs(start,graph):
        temp=[[start,{start}]]
        while temp:
            temp2=[]
            for j,k in temp:
                for i in graph[j]:
                    if i in k:
                        return j,k
                    else:
                        temp2.append([i,k|{i}])
            temp=temp2
        return None,None

    return_set_pre=set(range(n))
    for i in range(n):
        now,return_set=bfs(i,g)
        if return_set!=None:
            break
    if return_set==None:
        print(-1)
        return 0
    while True:
        for i in return_set_pre-return_set:
            g[i]={}
            g2[i]={}
        for i in return_set:
            g[i]=g[i]&return_set
            g2[i]=g2[i]&return_set
        l1=len([1 for i in range(n) if len(g[i])==1])
        l2=len([1 for i in range(n) if len(g2[i])==1])
        l=len(return_set)
        if l==l1 and l==l2:
            break
        return_set_pre=return_set
        now,return_set=bfs(now,g2)
        for i in return_set_pre-return_set:
            g[i]={}
            g2[i]={}
        for i in return_set:
            g[i]=g[i]&return_set
            g2[i]=g2[i]&return_set
        l1=len([1 for i in range(n) if len(g[i])==1])
        l2=len([1 for i in range(n) if len(g2[i])==1])
        l=len(return_set)
        if l==l1 and l==l2:
            break
        return_set_pre=return_set
        now,return_set=bfs(now,g)
    print(len(return_set))
    for i in return_set:
        print(i+1)
main()

Solution (Python):
n, m = map(int, input().split())
ans = [0] * (n + 1)
import collections
g = collections.defaultdict(set)

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

def minCircle(s):
    f = [None] * n
    visited = set()
    q = []
    q.append(s)
    while q:
        node = q.pop()
        for nei in g[node]:
            if nei not in visited:
                f[nei] = node
                visited.add(nei)
                q.append(nei)
        if s in visited:
            break
    p = f[s]
    ret = []
    ret.append(s)
    while p is not None and p!= s:
        ret.append(p)
        p = f[p]
    return ret

for i in range(n):
    t = minCircle(i)
    if len(t) > 1 and len(t) < len(ans):
        ans = t
if len(ans) == n + 1:
    print(-1)
else:
    print(len(ans))
    for i in ans:
        print(i+1)

Solution (Python):
n, m = map(int, input().split())
N = 1010
ans = [0] * (N +1)
g = [[] for _ in range(N)]

for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)



def minCircle(s):
    f = [0] * N
    visited = set()
    q = []
    q.append(s)
    while q:
        p = q.pop()
        for c in g[p]:
            if c not in visited:
                f[c] = p
                visited.add(c)
                q.append(c)
        if s in visited:
            break
    p = f[s]
    ret = []
    ret.append(s)
    while p and p!= s:
        ret.append(p)
        p = f[p]
    return ret

for i in range(1, n+1):
    t = minCircle(i)
    if len(t) > 1 and len(t) < len(ans):
        ans = t
if len(ans) == N+1:
    print(-1)
else:
    print(len(ans))
    for i in ans:
        print(i)

Solution (Python):
n, m = map(int, input().split())
N = 1010
ans = [0] * (N +1)
g = [[] for _ in range(N)]

for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)



def minCircle(s):
    f = [0] * N
    d = [0]* N
    q = []
    q.append(s)
    while q:
        p = q.pop()
        for c in g[p]:
            if not d[c]:
                f[c] = p
                d[c] = 1
                q.append(c)
        if d[s]:
            break
    p = f[s]
    ret = []
    ret.append(s)
    while p and p!= s:
        ret.append(p)
        p = f[p]
    return ret

for i in range(1, n+1):
    t = minCircle(i)
    if len(t) > 1 and len(t) < len(ans):
        ans = t
if len(ans) == N+1:
    print(-1)
else:
    print(len(ans))
    for i in ans:
        print(i)

Solution (Python):
n, m = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
vis = {}
def dfs(i):
    if i in vis:
        return vis[i]
    vis[i] = True
    for j in g[i]:
        if dfs(j):
            return True
    vis[i] = False
    return False
for i in range(n):
    if dfs(i):
        print(0)
        break
else:
    print(-1)