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

import sys
sys.setrecursionlimit(10**7)

def func(loop):
    sl=set(loop)
    k=len(loop)
    for i in range(k):
        v=loop[i]
        for nv in g[v]:
            if nv not in sl:continue
            if nv==loop[(i+1)%k]:continue
            j=[j for j in range(k) if loop[j]==nv][0]
            if i<j:
                ary=loop[:i+1]+loop[j:]
            else:
                ary=loop[j:i+1]
            func(ary)
    print(len(loop))
    for x in loop:
        print(x+1)
    exit()

mi=set(range(n))
def dfs(v,par):
    mi.discard(v)
    for nv in g[v]:
        if par[nv]==-1:
            par[nv]=v
            dfs(nv,par)
            par[nv]=-1
        else:
            loop=[v]
            while v!=nv:
                loop.append(par[v])
                v=par[v]
            loop.reverse()
            func(loop)
while mi:
    v=mi.pop()
    dfs(v,[-1]*n)
print(-1)

Solution (Python):
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
indeg = [0] * (n+1)
outdeg = [0] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indeg[b] += 1
    outdeg[a] += 1

is_valid = [indeg[i] * outdeg[i] for i in range(n+1)]
u = n+10
ans = []
from collections import deque
for start in range(1, n+1):
    if not is_valid[start]:
        continue

    
    q = deque([start])
    visited = [False] * (n+1)
    prev = [-1] * (n+1)
    visited[start] = True

    has_ans = False
    while q:
        now = q.popleft()
        
        for node in graph[now]:
            if node == start:
                
                prev[node] = now
                has_ans = True
                break
            if visited[node] or not is_valid[node]:
                continue
            
            prev[node] = now
            visited[node] = True
            q.append(node)
        if has_ans:
            break

    if not has_ans:
        continue
    cnt = 0
    tmp = []
    now = start
    for _ in range(n):
        tmp.append(now)
        cnt += 1
        now = prev[now]
        if now == start or now == -1:
            break
    if cnt < u:
        u = cnt
        ans = tmp

if ans:
    print(u)
    for t in ans:
        print(t)
else:
    print(-1)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)

    ans = []
    for i in range(N):
        queue = deque([i])
        dist = [-1] * N
        dist[i] = 0
        prev = [-1] * N
        while queue:
            v = queue.popleft()
            for nv in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    prev[nv] = v
                    queue.append(nv)
        for j in range(N):
            if i == j or dist[j] == -1 or i not in G[j]:
                continue
            tmp = []
            k = j
            while k != -1:
                tmp.append(k)
                k = prev[k]

            if not ans or len(ans) > len(tmp):
                ans = tmp

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

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)

    def dfs(v, p, seen, finished, hist):
        seen[v] = True
        hist.append(v)
        for nv in G[v]:
            if nv == p:
                continue
            if finished[nv]:
                continue
            if seen[nv] and not finished[nv]:
                return nv

            pos = dfs(nv, v, seen, finished, hist)
            if pos != -1:
                return pos
        hist.pop()
        finished[v] = True
        return -1

    for i in range(N):
        seen = [False] * N
        finished = [False] * N
        hist = []
        pos = dfs(i, -1, seen, finished, hist)
        if pos != -1:
            break

    if pos == -1:
        print(-1)
        return

    cycle = []
    while hist:
        t = hist.pop()
        cycle.append(t)
        if t == pos:
            break

    cycle.reverse()

    while True:
        order = [-1] * N
        for i, v in enumerate(cycle):
            order[v] = i

        for i, v in enumerate(cycle):
            ord_from = ord_to = -1
            for nv in G[v]:
                if v == nv or order[nv] == -1 or order[nv] == (order[v] + 1) % len(cycle):
                    continue
                ord_from, ord_to = i, order[nv]
                break
            if ord_from != -1:
                break

        if ord_from == -1:
            break

        if ord_from < ord_to:
            cycle = cycle[: ord_from + 1] + cycle[ord_to:]
        else:
            cycle = cycle[ord_to : ord_from + 1]

    print(len(cycle))
    for v in cycle:
        print(v + 1)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  G[a].append(b)
seen = [False]*n
def dfs(v):
  seen[v] = True
  for nv in G[v]:
    nxt[v] = nv
    if seen[nv]:
      return nv
    s = dfs(nv)
    if s != -1:
      return s
  seen[v] = False
  return -1
for i in range(n):
  nxt = [-1]*n
  s = dfs(i)
  if s != -1:
    break
else:
  print(-1)
  exit()
while True:
  used = set()
  L = []
  while s not in used:
    used.add(s)
    L.append(s)
    s = nxt[s]
  L.append(s)
  for i in range(len(L)-1):
    a, b = L[i], L[i+1]
    for nv in G[a]:
      if nv != b and nv in used:
        nxt[a] = nv
        s = a
        break
    else:
      continue
    break
  else:
    print(len(used))
    for v in used:
      print(v+1)
    break

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  G[a].append(b)
seen = [False]*n
def dfs(v):
  seen[v] = True
  for nv in G[v]:
    nxt[v] = nv
    if seen[nv]:
      return nv
    s = dfs(nv)
    if s != -1:
      return s
  seen[v] = False
  return -1
for i in range(n):
  nxt = [-1]*n
  s = dfs(i)
  if s != -1:
    break
else:
  print(-1)
  exit()
while True:
  used = set()
  L = []
  while s not in used:
    used.add(s)
    L.append(s)
    s = nxt[s]
  L.append(s)
  for i in range(len(L)-1):
    a, b = L[i], L[i+1]
    for nv in G[a]:
      if nv != b and nv in used:
        nxt[a] = nv
        s = a
        break
    else:
      continue
    break
  else:
    print(len(used))
    for v in used:
      print(v+1)
    break

Solution (Python):
from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n)]
INF = float('inf')
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)

res = []
shortest = n + 1
for s in range(n):
    dist = [-1] * n
    prev = [-1] * n
    q = deque()
    q.append(s)
    dist[s] = 0
    while len(q) != 0:
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                prev[nv] = v
                q.append(nv)
    for t in range(n):
        if t == s:
            continue
        if dist[t] == -1:
            continue
        for nt in g[t]:
            if nt == s:
                temp = [s]
                cur = t
                while cur != s:
                    temp.append(cur)
                    cur = prev[cur]
                if shortest > len(temp):
                    shortest = len(temp)
                    res = temp
if shortest == n + 1:
    print(-1)
    exit()
print(len(res))
for v in res:
    print(v + 1)

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

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


def find_loop(s, subnode):
    q = deque([(s, {s})])
    visited = defaultdict(lambda: math.inf)
    while len(q) > 0:
        node, p = q.popleft()
        for to_node in g[node] & subnode:
            if to_node == s:
                return p
            if visited[to_node] > len(p):
                visited[to_node] = len(p)
                q.append((to_node, p | {to_node}))
    return -1


V = set(range(N))
for i in range(N):
    subnode = find_loop(i, V)
    if subnode != -1:
        break
if subnode == -1:
    print(-1)
    sys.exit()


while True:
    
    flg = True
    for i in subnode:
        if len(g[i] & subnode) != 1:
            flg = False
            s = i
            break
    if flg:
        break
    subnode = find_loop(s, subnode)

print(len(subnode))
for node in subnode:
    print(node+1)

Solution (Python):
import sys
import io, os
input = sys.stdin.buffer.readline


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

from collections import deque
INF = 10**18
temp= INF
for a, b in edge:
    q = deque([])
    q.append(b)
    visit = [INF]*n
    visit[b] = 0
    par = [-1]*n
    while q:
        v = q.popleft()
        for u in g[v]:
            if visit[u] == INF:
                visit[u] = visit[v]+1
                par[u] = v
                q.append(u)
    if visit[a]+1 <= temp:
        ans = []
        v = a
        ans.append(v+1)
        while par[v] != -1:
            v = par[v]
            ans.append(v+1)
        temp =  visit[a]+1

if temp == INF:
    print(-1)
else:
    if ans:
        print(len(ans))
        print(*ans, sep='\n')
    else:
        print(-1)

Solution (Python):
import sys
import io, os
input = sys.stdin.buffer.readline


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

from collections import deque
INF = 10**18
temp= INF
for a, b in edge:
    q = deque([])
    q.append(b)
    visit = [INF]*n
    visit[b] = 0
    par = [-1]*n
    while q:
        v = q.popleft()
        for u in g[v]:
            if visit[u] == INF:
                visit[u] = visit[v]+1
                par[u] = v
                q.append(u)
    if visit[a]+1 <= temp:
        ans = []
        v = a
        ans.append(v+1)
        while par[v] != -1:
            v = par[v]
            ans.append(v+1)
        temp =  visit[a]+1

if temp == INF:
    print(-1)
else:
    if ans:
        print(len(ans))
        print(*ans, sep='\n')
    else:
        print(-1)

Solution (Python):

from collections import deque
def resolve():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, input().split())
        G[a].append(b)

    shortest = N + 1
    res = []
    for s in range(N):
        dist = [-1] * N
        pre = [-1] * N
        q = deque()
        q.append(s)
        dist[s] = 0
        while q:
            v = q.popleft()
            for to in G[v]:
                if dist[to] == -1:
                    dist[to] = dist[v] + 1
                    pre[to] = v
                    q.append(to)

        for t in range(N):
            if t == s or dist[t] == -1:
                continue
            for to in G[t]:
                if to == s:  
                    tmp = [s]
                    cur = t
                    while cur != s:
                        tmp.append(cur)
                        cur = pre[cur]
                    if shortest > len(tmp):
                        shortest = len(tmp)
                        res = tmp

    if shortest == N + 1:
        print(-1)
    else:
        print(len(res))
        res.sort()
        for v in res:
            print(v + 1)


if __name__ == "__main__":
    resolve()

Solution (Python):
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 func(path):
  chk=set(path)
  if len(path)!=2:
    for i,v in enumerate(path):
      nvs=[nv for nv in g[v] if nv in chk]
      if len(nvs)==1:continue
      for nv in nvs:
        if nv==path[(i+1)%len(path)]:continue
        ary=[nv]
        for j,vj in enumerate(path):
          if vj==nv:break
        if i>j:
          ary=path[j:i+1]
        else:
          ary=path[:i+1]+path[j:]
        
        func(ary)
  print(len(path))
  for v in path:
    print(v+1)
  exit()

def dfs(v,seen):
  mi.discard(v)
  for nv in g[v]:
    if seen[nv]!=-1:
      seen[nv]=v
      path=[v]
      chk={v}
      while seen[v] not in chk:
        v=seen[v]
        path.append(v)
        chk.add(v)
      path.reverse()
      func(path)
    else:
      seen[nv]=v
      dfs(nv,seen)
      seen[nv]=-1
while mi:
  v=mi.pop()
  seen=[-1]*n
  dfs(v,seen)
print(-1)
exit()

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


from collections import deque

def main():
	n,m=MI()
	G=[[] for _ in range(n+1)]

	for _ in range(m):
		a,b=MI()
		G[a].append(b)

	A=[10**5]*(n+1)

	for i in range(1,n+1):
		Q=deque([[i,0]])
		D=[-1]*(n+1)
		while Q:
			
			now,d=Q.popleft()
			if now==i and d>0:
				A[i]=d
				break
			for nx in G[now]:
				if D[nx]==-1:
					D[nx]=d+1
					Q.append([nx,d+1])
	

	k=min(A)
	

	if k==10**5:
		print(-1)
		exit()

	s=A.index(k)
	

	A=[]
	Q=deque([[s,0]])
	D=[10**5]*(n+1)

	while Q:
		now,d=Q.pop()
		if now==s and d>0:
			break
		if d==k:
			continue
		A.append(now)
		for nx in G[now]:
			if D[nx]>d+1:
				D[nx]=d+1
				Q.append([nx,d+1])
	D[s]=0

	
	

	ans=[]
	d=k-1
	for i in reversed(A):
		if D[i]==d:
			ans.append(i)
			d-=1

	print(k)
	print(*ans[::-1],sep="\n")










if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


from collections import deque

def main():
	n,m=MI()
	G=[[] for _ in range(n+1)]

	for _ in range(m):
		a,b=MI()
		G[a].append(b)

	A=[10**5]*(n+1)

	for i in range(1,n+1):
		Q=deque([[i,0]])
		D=[-1]*(n+1)
		while Q:
			
			now,d=Q.popleft()
			if now==i and d>0:
				A[i]=d
				break
			for nx in G[now]:
				if D[nx]==-1:
					D[nx]=d+1
					Q.append([nx,d+1])
	

	k=min(A)
	

	if k==10**5:
		print(-1)
		exit()

	s=A.index(k)
	

	A=[]
	Q=deque([[s,0]])
	D=[10**5]*(n+1)

	while Q:
		now,d=Q.pop()
		if now==s and d>0:
			break
		if d==k:
			continue
		A.append(now)
		for nx in G[now]:
			if D[nx]>d+1:
				D[nx]=d+1
				Q.append([nx,d+1])
	D[s]=0

	
	

	ans=[]
	d=k-1
	for i in reversed(A):
		if D[i]==d:
			ans.append(i)
			d-=1

	print(k)
	print(*ans[::-1],sep="\n")










if __name__ == "__main__":
	main()

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

def main():
    n, m = map(int, input().split())
    
    tree = [[] for _ in range(n)]
    edge = dict()
    for i in range(m):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        edge[(a-1, b-1)] = i+1
    
    ans = 0
    for i in range(n):
        not_yet = deque([i])
        already = [False]*n
        dist = [0]*n
        par = [0]*n
        already[i] = True
        sub = []
        
        while not_yet:
            key = not_yet.popleft()
            for v in tree[key]:
                if already[v]:
                    
                    if v == i:
                        sub = [key+1]
                        now = key
                        while now != i:
                            sub.append(par[now]+1)
                            now = par[now]
                        break
                    continue
                
                not_yet.append(v)
                already[v] = True
                dist[v] = dist[key] + 1
                par[v] = key
            if sub:
                break
            
        if sub:
            if ans:
                if len(ans) > len(sub):
                    ans = copy(sub)
            else:
                ans = copy(sub)
            
        
    if ans:
        print(len(ans))
        for a in ans:
            print(a)
    else:
        print(-1)
        
    
    
if __name__ == "__main__":
    main()

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

def main():
    n, m = map(int, input().split())
    
    tree = [[] for _ in range(n)]
    edge = dict()
    for i in range(m):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        edge[(a-1, b-1)] = i+1
    
    ans = 0
    for i in range(n):
        not_yet = deque([i])
        already = [False]*n
        dist = [0]*n
        par = [0]*n
        already[i] = True
        sub = []
        
        while not_yet:
            key = not_yet.popleft()
            for v in tree[key]:
                if already[v]:
                    
                    if v == i:
                        sub = [key+1]
                        now = key
                        while now != i:
                            sub.append(par[now]+1)
                            now = par[now]
                        break
                    continue
                
                not_yet.append(v)
                already[v] = True
                dist[v] = dist[key] + 1
                par[v] = key
            if sub:
                break
            
        if sub:
            if ans:
                if len(ans) > len(sub):
                    ans = copy(sub)
            else:
                ans = copy(sub)
            
        
    if ans:
        print(len(ans))
        for a in ans:
            print(a)
    else:
        print(-1)
        
    
    
if __name__ == "__main__":
    main()

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

def DD(arg): return defaultdict(arg)
INF = float('inf')

N,M = list(map(int,input().split()))
graph = {i:[] for i in range(N)}
for _ in range(M):
  a,b = list(map(int,input().split()))
  graph[a-1].append(b-1)
p = [None for i in range(N)]
def detect_cycle(graph):
  N = len(graph)
  Q = [i for i in range(N)]
  cycle = []
  while Q:
    state = [-1 for i in range(N)]
    s = Q.pop()
    if p[s] != None: continue
    p[s] = -1
    q = [s]
    while q:
      x = q.pop()
      if x < 0:
        state[~x] = 0
        continue
      q.append(~x)
      for y in graph[x]:
        state[x] = 1
        if state[y] == 0: continue
        elif state[y] == -1:
          p[y] = x
          q.append(y)
        else:
          p[y] = x
          now = x
          while now != y:
            cycle.append(now)
            now = p[now]
          cycle.append(y)
          return cycle
  return cycle

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)

c = detect_cycle(graph)
if not c:
  print(-1)
else:
  squeeze(c)

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

def DD(arg): return defaultdict(arg)
INF = float('inf')

N,M = list(map(int,input().split()))
graph = {i:[] for i in range(N)}
for _ in range(M):
  a,b = list(map(int,input().split()))
  graph[a-1].append(b-1)
p = [None for i in range(N)]
def detect_cycle(graph):
  N = len(graph)
  Q = [i for i in range(N)]
  
  cycle = []
  while Q:
    state = [-1 for i in range(N)]
    FLAG = 0
    s = Q.pop()
    if p[s] != None: continue
    p[s] = -1
    q = [s]
    while q:
      flag = 0
      x = q.pop()
      if x < 0:
        state[~x] = 0
        continue
      q.append(~x)
      for y in graph[x]:
        state[x] = 1
        if state[y] == 0: continue
        elif state[y] == -1:
          p[y] = x
          q.append(y)
        else:
          p[y] = x
          now = x
          while now != y:
            cycle.append(now)
            now = p[now]
          cycle.append(y)
          flag = 1
          break
      if flag:
        FLAG = 1
        break
    if FLAG:
      break
  return cycle

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)

c = detect_cycle(graph)
if not c:
  print(-1)
else:
  squeeze(c)

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

def DD(arg): return defaultdict(arg)
INF = float('inf')

N,M = list(map(int,input().split()))
graph = {i:[] for i in range(N)}
for _ in range(M):
  a,b = list(map(int,input().split()))
  graph[a-1].append(b-1)
  
Q = [i for i in range(N)]
p = [None for i in range(N)]
heiro = []
while Q:
  state = [-1 for i in range(N)]
  Flag = 0
  s = Q.pop()
  if p[s] != None: continue
  p[s] = -1
  q = [s]
  while q:
    flag = 0
    x = q.pop()
    if x < 0:
      state[~x] = 0
      continue
    q.append(~x)
    for y in graph[x]:
      state[x] = 1
      if state[y] == -1:
        p[y] = x
        q.append(y)
      elif state[y] == 0:
        continue
      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):
  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 y in l:
        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)

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

def DD(arg): return defaultdict(arg)
INF = float('inf')

N,M = list(map(int,input().split()))
graph = {i:[] for i in range(N)}
for _ in range(M):
  a,b = list(map(int,input().split()))
  graph[a-1].append(b-1)
  
Q = [i for i in range(N)]
p = [None for i in range(N)]
heiro = []
while Q:
  state = [-1 for i in range(N)]
  Flag = 0
  s = Q.pop()
  if p[s] != None: continue
  p[s] = -1
  q = [s]
  while q:
    flag = 0
    x = q.pop()
    if x < 0:
      state[~x] = 0
      continue
    q.append(~x)
    for y in graph[x]:
      state[x] = 1
      if state[y] == -1:
        p[y] = x
        q.append(y)
      elif state[y] == 0:
        continue
      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)