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
import sys
sys.setrecursionlimit(10**6)

class DirectedGraph:
    def __init__(self, adj):
        self.n = len(adj)
        self.adj = adj
        self.is_asyclic = False
        self.max_path_len = None

    def topological_sort(self):
        indegree = [0] * self.n
        for i, vs in enumerate(self.adj):
            for dest in vs:
                indegree[dest] += 1
        zero_v = []
        for v, indeg in enumerate(indegree):
            if indeg == 0:
                zero_v.append(v)
        max_path_len = 1
        tp_sorted = []
        to_be_added = []
        while True:
            while zero_v:
                v = zero_v.pop()
                tp_sorted.append(v)
                for dest in self.adj[v]:
                    indegree[dest] -= 1
                    if indegree[dest] == 0:
                        to_be_added.append(dest)
            if len(to_be_added) > 0:
                zero_v += to_be_added
                to_be_added = []
                max_path_len += 1
            else:
                break
        if len(tp_sorted) == self.n:
            self.is_asyclic = True
            self.max_path_len = max_path_len
            return tp_sorted
        else:
            self.is_asyclic = False
            return None

    def extract_cycle(self):
        self.seen = [0] * self.n
        self.checked = [0] * self.n
        self.hist = deque()
        self.node_in_cycle = -1

        def dfs(v):
            self.seen[v] = 1
            self.hist.append(v)
            for nv in self.adj[v]:
                if self.checked[nv]:
                    continue
                if self.seen[nv] and not self.checked[nv]:
                    self.node_in_cycle = nv
                    return
                dfs(nv)
                if self.node_in_cycle != -1:
                    return
            self.hist.pop()
            self.checked[v] = 1

        for i in range(self.n):
            if not self.checked[i]:
                dfs(i)
            if self.node_in_cycle != -1:
                break
        if self.node_in_cycle == -1:
            return []
        else:
            cycle = []
            while self.hist:
                t = self.hist.pop()
                cycle.append(t)
                if t == self.node_in_cycle:
                    break
            cycle.reverse()
            return cycle

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

DG = DirectedGraph(edge)
cycle = DG.extract_cycle()

if len(cycle) == 0:
    print(-1)
    exit()

while True:
    in_cycle = set(cycle)
    deg = [0] * n 
    for item in cycle:
        for v in edge[item]:
            if v in in_cycle:
                deg[v] += 1
    
    ok = True
    for i, item in enumerate(cycle):
        if deg[item] > 1:
            ok = False
            cur_id = start = i
    if ok:
        print(len(cycle))
        print("\n".join([str(item + 1) for item in cycle]))
        exit()

    ncycle = []
    cur = cycle[cur_id]
    while True:
        ncycle.append(cur)
        if cycle[start] in edge[cur]:
            break
        cur_id = (cur_id + 1) % len(cycle)
        cur = cycle[cur_id]
    cycle = ncycle[:]

Solution (Python):
from collections import deque

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

seen = [0] * n
checked = [0] * n
hist = deque()
ret = -1
def dfs(v):
    global ret
    seen[v] = 1
    hist.append(v)
    for nv in edge[v]:
        if checked[nv]: 
            continue
        if seen[nv] and not checked[nv]:
            ret = nv
            return
        dfs(nv)
        if ret != -1: 
            return
    hist.pop()
    checked[v] = 1

for i in range(n):
    dfs(i)
    if ret != -1:
        break

if ret == -1:
    print(-1)
    exit()

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

while True:
    in_cycle = set(cycle)
    deg = [0] * n 
    for item in cycle:
        for v in edge[item]:
            if v in in_cycle:
                deg[v] += 1
    
    ok = True
    for i, item in enumerate(cycle):
        if deg[item] > 1:
            ok = False
            cur_id = start = i
    if ok:
        print(len(cycle))
        print("\n".join([str(item + 1) for item in cycle]))
        exit()

    ncycle = []
    cur = cycle[cur_id]
    while True:
        ncycle.append(cur)
        if cycle[start] in edge[cur]:
            break
        cur_id = (cur_id + 1) % len(cycle)
        cur = cycle[cur_id]
    cycle = ncycle[:]

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N, M = [int(i) for i in input().split()]


for i in range(M):
    u, v = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, 1)
    g.add_edge(u-1+N, v-1, 1)
    g.add_edge(u-1, v-1+N, 1)

d = Dijkstra(g, 0)

ans_n = 10 ** 6
ans_index = -1
for i in range(N):
    d = Dijkstra(g, i)
    ans_n_ = d.dist[i+N]

    if ans_n_ < ans_n:
        ans_index = i
        ans_n = ans_n_

if ans_n == 10 ** 6:
    print(-1)
else:
    d = Dijkstra(g, ans_index)
    ans = d.shortest_path(ans_index + N)
    ans.sort()
    print(ans_n)
    for j in range(ans_n):
        print(ans[j]+1)

Solution (Python):
def main():
  from collections import deque
  n,m,*t=map(int,open(0).read().split())
  i=[0]*n
  o=[[]for _ in range(n)]
  for a,b in zip(*[iter(t)]*2):
    o[a-1]+=b-1,
    i[b-1]+=1
  q=deque(v for v,f in enumerate(i)if f<1)
  r=[]
  while q:
    v=q.popleft()
    r+=v,
    for w in o[v]:
      i[w]-=1
      if i[w]==0:q+=w,
  print(-(len(r)==n))
main()

Solution (Python):
def main():
  from collections import deque
  n,m,*t=map(int,open(0).read().split())
  i,o=[0]*n,[[]for _ in range(n)]
  for a,b in zip(*[iter(t)]*2):
    o[a-1]+=b-1,
    i[b-1]+=1
  q=deque(v for v in range(n)if i[v]<1)
  r=[]
  while q:
    v=q.popleft()
    r+=v,
    for w in o[v]:
      i[w]-=1
      if i[w]==0:q+=w,
  print(-(len(r)==n))
main()

Solution (Python):
from collections import*
n,m,*t=map(int,open(0).read().split())
i,o=[0]*n,[[]for _ in range(n)]
for a,b in zip(*[iter(t)]*2):
  o[a-1]+=b-1,
  i[b-1]+=1
q=deque(v for v in range(n)if i[v]<1)
r=[]
while q:
  v=q.popleft()
  r+=v,
  for w in o[v]:
    i[w]-=1
    if i[w]==0:q+=w,
print(-(len(r)==n))

Solution (Python):
from collections import*
n,m=map(int,input().split())
outs=defaultdict(list)
ins=defaultdict(int)
for _ in range(m):
    a,b=map(int,input().split())
    outs[a-1]+=b-1,
    ins[b-1]+=1
q=deque(i for i in range(n)if ins[i]==0)
res=[]
while q:
    v=q.popleft()
    res+=v,
    for w in outs[v]:
        ins[w]-=1
        if ins[w]==0:
            q.append(w)
print(-(len(res)==n))

Solution (Python):
from collections import*
n,m=map(int,input().split())
outs=defaultdict(list)
ins=defaultdict(int)
for _ in range(m):
    a,b=map(int,input().split())
    outs[a-1]+=b-1,
    ins[b-1]+=1
q=deque(i for i in range(n)if ins[i]==0)
res=[]
while q:
    v=q.popleft()
    res+=v,
    for w in outs[v]:
        ins[w]-=1
        if ins[w]==0:
            q.append(w)
print(-(len(res)==n))

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    es[a].append(b)
ansr, ansd = -1, INF
for r in range(1, N+1):
    d = [INF] * (N+1)
    d[0] = 0
    dq = deque()
    for w in es[r]:
        dq.append(w)
        d[w] = 1
    while len(dq) > 0:
        v = dq.popleft()
        if v == r:
            break
        nd = d[v]+1
        for u in es[v]:
            if nd < d[u]:
                d[u] = nd
                dq.append(u)
    if d[r] < ansd:
        ansd = d[r]
        ansr = r
if ansr == -1:
    print(-1)
else:
    vis = [0] * (N+1)
    vis[0] = 1
    p = [-1] * (N+1)
    dq = deque()
    for v in es[ansr]:
        vis[v] = 1
        p[v] = 0
        dq.append(v)
    while len(dq) > 0:
        v = dq.popleft()
        if v == ansr:
            break
        for u in es[v]:
            if vis[u] == 0:
                vis[u] = 1
                p[u] = v
                dq.append(u)
    lst = []
    v = ansr
    while p[v] != -1:
        lst.append(v)
        v = p[v]
    print(len(lst))
    print(*lst, sep = '\n')

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

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

graph = [[] for _ in range(N)]

for i in range(M):
	A, B = list(map(int, input().split()))
	A -= 1
	B -= 1
	graph[A].append(B)


for start in range(N):
	parent = [-1] * N
	depth = [0] * N
	que = deque([])
	que.append(start)
	depth[start] = 1
	while len(que) > 0:
		node = que.popleft()
		judge = 0
		if len(graph[node]) > 0:
			for node_next in graph[node]:
				if depth[node_next] == 1:
					judge = 1
				if depth[node_next] == 0:
					depth[node_next] = depth[node] + 1
					que.append(node_next)
					parent[node_next] = node
		if judge == 1:
			last = node
			break
	if judge == 1:
		break


if judge != 1:
	print(-1)
	exit()

node_list = deque([last])
while True:
	loc = parent[node_list[0]]
	if loc == -1:
		break
	else:
		node_list.appendleft(loc)

node_set = set([node_list[0]])


for i in range(1, len(node_list)):
	max_depth = -1
	for edge in graph[node_list[i]]:
		if edge in node_set:
			for j in range(i):
				if edge == node_list[j]:
					max_depth = max(max_depth, j)
	if max_depth >= 0:
		start = max_depth
		end = i
		break
	node_set.add(node_list[i])


print(end + 1 - start)
for node in range(start, end + 1):
	print(node_list[node] + 1)

Solution (Python):
from collections import deque
from copy import deepcopy



def detect_cycle(N, repn):
    color = ['WHITE'] * (N + 1)
    unfinished_vertex = set([i for i in range(1, N + 1)])
    cycle = []
    Repn = deepcopy(repn)

    def dfs(u0):
        deq = deque([u0])
        color[u0] = 'GRAY'

        while deq != deque([]) and cycle == []:
            u = deq[-1]
            if len(Repn[u]) != 0:
                v = Repn[u].popleft()
                if color[v] == 'WHITE':
                    color[v] = 'GRAY'
                    deq.append(v)
                elif color[v] == 'GRAY':
                    cycle.append(v)
            else:
                deq.pop()
                color[u] = 'BLACK'
                unfinished_vertex.remove(u)

        return deq

    while cycle == [] and unfinished_vertex != set([]):
        u = unfinished_vertex.pop()
        unfinished_vertex.add(u)
        deq = dfs(u)
        
    
    if cycle != []:
        v = cycle.pop()
        while True:
            u = deq.pop()
            cycle.append(u)
            if u == v:
                break
        cycle.reverse()
        return cycle 
    else:
        return []


def minimize_cycle(cycle, repn):
    length = len(cycle)
    cycle_idx = {u : i for i, u in enumerate(cycle)}
    minimized = False

    for i, u in enumerate(cycle):
        if minimized == True:
            break
        else:
            for v in repn[u]:
                if v in cycle_idx.keys():
                    j = cycle_idx[v]
                    if i + 1 == j:
                        continue
                    elif i == length - 1 and j == 0:
                        continue
                    elif i < j:
                        reduced_cycle = cycle[:(i + 1)] + cycle[j:]
                        minimized = True
                        break
                    else:
                        reduced_cycle = cycle[j:(i + 1)]
                        minimized = True
                        break

    if minimized == True:
        return reduced_cycle, minimized
    else:
        return cycle, minimized


def main():
    N, M = map(int, input().split())
    repn = [deque([]) for i in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        repn[a].append(b)

    cycle = detect_cycle(N, repn)
    
    if cycle == []:
        print(-1)
        exit()

    minimized = True
    while minimized == True:
        cycle, minimized = minimize_cycle(cycle, repn)
        

    print(len(cycle))
    for u in cycle:
        print(u)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from io import StringIO
import unittest
import heapq
class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4 5
1 2
2 3
2 4
4 1
4 3"""
        output = """3
1
2
4"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4 5
1 2
2 3
2 4
1 4
4 3"""
        output = """-1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2"""
        output = """4
2
3
4
5"""
        self.assertIO(input, output)



def resolve():
    (N,M)=(int(i) for i in input().split())
    graph=[[[],[]] for i in range(N)]
    for i in range(M):
        (a,b)=(int(i)-1 for i in input().split())
        graph[a][0].append(b)
        graph[b][1].append(a)
    flg=True
    element=[True for i in range(N)]
    while flg:
        flg=False
        for i in range(N):
            if element[i]==False:
                continue
            if graph[i][0]==[]:
                for j in graph[i][1]:
                    graph[j][0].remove(i)
                flg=True
                graph[i][1]=[]
                element[i]=False
            if graph[i][1]==[]:
                for j in graph[i][0]:
                    graph[j][1].remove(i)
                flg=True
                graph[i][0]=[]
                element[i]=False




    def dicstra(i):

        cost=[100000 for _ in graph]
        cost[i]=0

        oya=[[] for _ in graph]
        muki = [j[0] for j in graph]

        visited=[False for j in muki]
        q=[]
        heapq.heappush(q,[0,i])
        while q:
            c,ind=heapq.heappop(q)
            visited[ind]=True
            oya[ind].append(ind)
            for j in muki[ind]:
                if (not visited[j]) and  cost[j]>cost[ind]+1:
                    cost[j]=cost[ind]+1
                    oya[j]=oya[ind][:]
                    heapq.heappush(q,[cost[j],j])
        xx=[oya[j] for j in graph[i][1]]
        xx.sort(key=lambda it: len(it))


        for j in xx[0]:
            for k in range(len(graph[j][0])):
                if k>=len(graph[j][0]):
                    break                
                x=graph[j][0][k]
                if not (x in xx[0]):
                    graph[j][0].remove(x)
                    if k>=len(graph[j][0]):
                        break
            for k in range(len(graph[j][1])):
                if k>=len(graph[j][1]):
                        break
                x=graph[j][1][k]
                if not (x in xx[0]):

                    graph[j][1].remove(x)

            if len(graph[j][1])>1:

                return j
                
        else:
            print(len(xx[0]))
            for i in xx[0]:
                print(i+1)
            return -1
    for i in range(N):
        if element[i]:
            while i>=0:
                
                i = dicstra(i)
            
            
            break
    else:
        print(-1)



if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
from collections import deque
from collections import defaultdict
import copy

n, m = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(n+1)]
radj = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    adj[a].append(b)
    radj[b]


def searchRoute(i):
    global adj
    nexts = deque()
    route = [i]
    visited = set()
    result = []
    for x in adj[i]:
        if x < i:
            continue
        nroute = copy.copy(route)
        nexts.append((x, nroute))
    while len(nexts) > 0:
        error = False
        found = False
        x, xroute = nexts.popleft()
        xroute.append(x)
        visited.add(x)
        for y in adj[x]:
            if y < i:
                continue
            if y == i:
                found = True
                break
            if y in visited:
                break
            yroute = copy.copy(xroute)
            nexts.append((y, yroute))
        if found:
            result = xroute
            break
    return result

heiro = []
for i in range(1, n+1):
    res = searchRoute(i)
    if len(res) > 0:
        heiro = res
        break

if len(heiro) == 0:
    print(-1)
    exit()
while True:
    visited = set()
    bp = [-1, -1]
    rt = defaultdict(int)
    for i in range(len(heiro)):
        visited.add(heiro[i])
        rt[heiro[i]] = i
        for j in adj[heiro[i]]:
            if j in visited and not (i == len(heiro) - 1 and j == heiro[0]):
                bp = [i, rt[j]]
                break
        if bp[0] != -1:
            break
    if bp[0] == -1:
        print(len(heiro))
        for i in heiro:
            print(i)
        exit()
    heiro = heiro[bp[1]:bp[0]+1]

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

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

edge = [[] for _ in [0]*n]
back = [[] for _ in [0]*n]

for _ in [0]*m:
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    back[b-1].append(a-1)


res = [None]*(n+1)

for end in range(n):
    for start in edge[end]:
        cost = [-1]*n
        cost[start] = 0
        new = [start]
        tank = []
        judge = True

        while len(new) > 0 and judge:
            tank = []
            for fr in new:
                for go in edge[fr]:
                    if cost[go] < 0:
                        cost[go] = cost[fr] + 1
                        tank.append(go)
                        if go == end:
                            judge = False
            new = tank

        
        if cost[end] >= 0 and cost[end] < len(res):
            p = end
            res = [p+1]
            while p != start:
                for e in back[p]:
                    if cost[p] == cost[e]+1:
                        p = e
                        res.append(p+1)
                        break
if res[0] == None:
    print(-1)
else:                      
    print(len(res))
    for e in res:
        print(e)

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

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)

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            print(-99999)
            exit()
        else:
            search_path(x, temp + [x])


t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(i, [i])

print(-1)

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

def main():

    def loopfind():
        for i in range(N):
            if USE[i]==1:
                break
        else:
            return []
        
        Q=deque()
        Q.append(i)
        USESET={i}
        ANS=[i]

        while True:
            for to in EOUTLIST[ANS[-1]]:
                if USE[to]==1:
                    nextv=to
                    break

            if nextv in USESET:
                break
            else:
                ANS.append(nextv)
                USESET.add(nextv)

        x=ANS.index(nextv)
        return ANS[x:]

    def shortcut(ANS):
        

        ANSSET=set(ANS)
        LEN=len(ANS)
        flag=0

        for i in range(LEN):
            for to in EOUTLIST[ANS[i]]:
                if to in ANSSET and ANS[(i+1)%LEN]!=to:
                    flag=1
                    x=ANS.index(to)

                    

                    break
            if flag:
                break
        

        if flag:
            if x<i:
                return shortcut(ANS[x:i+1])
            else:
                return shortcut(ANS[x:]+ANS[:i+1])

        else:
            return ANS
    
    N,M=map(int,input().split())

    EIN=[0]*N
    EOUT=[0]*N

    EINLIST=[[] for i in range(N)]
    EOUTLIST=[[] for i in range(N)]

    for i in range(M):
        x,y=map(int,input().split())
        x-=1
        y-=1

        EOUT[x]+=1
        EIN[y]+=1

        EOUTLIST[x].append(y)
        EINLIST[y].append(x)

    Q=deque()
    USE=[1]*N

    for i in range(N):
        if EIN[i]==0 or EOUT[i]==0:
            Q.append(i)
            USE[i]=0

    while Q:
        x=Q.pop()

        for to in EOUTLIST[x]:
            if USE[to]==0:
                continue
            EIN[to]-=1
            if EIN[to]==0:
                Q.append(to)
                USE[to]=0

        for fr in EINLIST[x]:
            if USE[fr]==0:
                continue
            EOUT[fr]-=1
            if EOUT[fr]==0:
                Q.append(fr)
                USE[fr]=0

    ANS=shortcut(loopfind())
    if len(ANS)==0:
        print(-1)
    else:
        print(len(ANS))
        for ans in ANS:
            print(ans+1)

main()

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 sys
input = sys.stdin.readline

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

EIN=[0]*N
EOUT=[0]*N

EINLIST=[[] for i in range(N)]
EOUTLIST=[[] for i in range(N)]

for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1

    EOUT[x]+=1
    EIN[y]+=1

    EOUTLIST[x].append(y)
    EINLIST[y].append(x)

from collections import deque

Q=deque()
USE=[1]*N

for i in range(N):
    if EIN[i]==0 or EOUT[i]==0:
        Q.append(i)
        USE[i]=0

while Q:
    x=Q.pop()

    for to in EOUTLIST[x]:
        if USE[to]==0:
            continue
        EIN[to]-=1
        if EIN[to]==0:
            Q.append(to)
            USE[to]=0

    for fr in EINLIST[x]:
        if USE[fr]==0:
            continue
        EOUT[fr]-=1
        if EOUT[fr]==0:
            Q.append(fr)
            USE[fr]=0
            
def loopfind():
    for i in range(N):
        if USE[i]==1:
            break
    else:
        return []
    
    Q=deque()
    Q.append(i)
    USESET={i}
    ANS=[i]

    while True:
        for to in EOUTLIST[ANS[-1]]:
            if USE[to]==1:
                nextv=to
                break

        if nextv in USESET:
            break
        else:
            ANS.append(nextv)
            USESET.add(nextv)

    x=ANS.index(nextv)
    return ANS[x:]
        

def shortcut(ANS):
    

    ANSSET=set(ANS)
    LEN=len(ANS)
    flag=0

    for i in range(LEN):
        for to in EOUTLIST[ANS[i]]:
            if to in ANSSET and ANS[(i+1)%LEN]!=to:
                flag=1
                x=ANS.index(to)

                

                break
        if flag:
            break
    

    if flag:
        if x<i:
            return shortcut(ANS[x:i+1])
        else:
            return shortcut(ANS[x:]+ANS[:i+1])

    else:
        return ANS

ANS=shortcut(loopfind())
if len(ANS)==0:
    print(-1)
else:
    print(len(ANS))
    for ans in ANS:
        print(ans+1)

Solution (Python):
def f_pure():
    
    from collections import deque
    N, M = [int(i) for i in input().split()]

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

    shortest = N + 1
    ans = []
    for s in range(N):
        
        dist = [-1] * N
        previous = [-1] * N  
        queue = deque([s])
        dist[s] = 0
        while queue:
            v = queue.pop()
            for next_node in graph[v]:
                if dist[next_node] == -1:
                    dist[next_node] = dist[v] + 1
                    previous[next_node] = v
                    queue.appendleft(next_node)

        for t in range(N):
            if t == s or dist[t] == -1:
                continue  
            for next_node in graph[t]:
                if next_node == s:  
                    ans_tmp = [s]  
                    current_node = t
                    
                    while current_node != s:
                        ans_tmp.append(current_node)
                        current_node = previous[current_node]
                    
                    if shortest > len(ans_tmp):
                        shortest = len(ans_tmp)
                        ans = ans_tmp

    if shortest == N + 1:
        return -1  
    return ' '.join(map(str, [len(ans)] + sorted(v + 1 for v in ans)))

print(f_pure())

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)
deg=[0 for i in range(N)]
for i in range(N):
	for p in G[i]:
		deg[p]+=1
q=deque(i for i in range(N) if deg[i]==0)
res=[]
while q:
	u=q.popleft()
	res.append(u)
	for v in G[u]:
		deg[v]-=1
		if deg[v]==0:
			q.append(v)
if len(res)==N:
	print(-1)
	exit()
X={i for i in range(N)}
for st in range(N):
	pre=[-1 for i in range(N)]
	q=deque([st])
	flag=0
	while(q):
		r=q.popleft()
		for p in G[r]:
			if pre[p]==-1:
				pre[p]=r
				q.append(p)
			if pre[st]!=-1:
				Y={st}
				tmp=pre[st]
				while(tmp!=st):
					Y.add(tmp)
					tmp=pre[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):
from heapq import heappop, heappush

n, m = map(int, input().split())
xy = [tuple(int(x)-1 for x in input().split()) for _ in range(m)]

R = [[] for _ in range(n)]
h = [0] * n

for x, y in xy:
    R[x].append(y)
    h[y] += 1

S = []

st = []

for i in range(n):
    if h[i] == 0:
        heappush(st, i)

while len(st) > 0:
    temp = heappop(st)
    S.append(temp)
    for x in R[temp]:
        h[x] -= 1
        if h[x] == 0:
            heappush(st, x)

if len(S) != n:
    print(-99999)
else:
    print(-1)

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

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)

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            print(-99999)
            exit()
        else:
            search_path(x, temp + [x])


t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(i, [i])

print(-1)