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*
n,m,*t=map(int,open(0).read().split())
i,o,r=[0]*n,[[]for _ in'_'*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)
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):
n, m = map(int, input().split())

g = [[] for _ in range(1005)]

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

vis = [0] * 1005


def dfs(x, p):
    if vis[x]:
        return []
    p.append(x)
    vis[x] = 1
    for v in g[x]:
        if v in p:
            return p
        t = dfs(v, p)
        if len(t):
            return t
    p.pop()
    return []


t = []
for i in range(1, 1 + n):
    t = dfs(i, [])
    if len(t):
        print(0)
        exit(0)

print(-1)

Solution (Python):
from collections import*
n,m,*t=map(int,open(0).read().split())
i,o,r=[0]*n,[[]for _ in'_'*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)
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,*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):

INF = 1001001001
n, m = map(int, input().split())
 
def bfs(sv, to_list):
  dist = [INF for i in range(n)]
  hist = [-1 for i in range(n)]
  q = []
  dist[sv] = 0
  q.append(sv)
  while len(q) > 0:
    v = q[0]
    del q[0]
    for j in to_list[v]:
      if dist[j] != INF:
        continue
      hist[j] = v
      dist[j] = dist[v] + 1
      q.append(j)
  min_cycle = INF
  min_hist = -1
  for i in range(n):
    if i == sv:
      continue
    for j in to[i]:
      if j == sv:
        if min_cycle > dist[i]:
          min_cycle = dist[i]
          min_hist = i
  res = []
  temp_v = min_hist
  if min_cycle < INF:
    while temp_v > -1:
      res.append(temp_v)
      temp_v = hist[temp_v]
  else:
    res = [1 for i in range(n+1)]
  return res
    
 
to = [[] for i in range(m)]
for i in range(m):
  a, b = map(int, input().split())
  to[a-1].append(b-1)
if len(to) == 0:
  print(-1)
else:  
  c = [bfs(i, to) for i in range(n)]
  ans = [1 for i in range(n+1)]
  for i in range(n):
    if len(ans) > len(c[i]):
      ans = c[i]
  if len(ans) == n + 1:
    print(-1)
  else:
    print(len(ans))
    for v in ans[::-1]:
      print(v+1)

Solution (Python):
import sys
from collections import deque


def shave(fwd_link, bwd_link):
    
    q = [v for v, links in enumerate(fwd_link) if not links]
    while q:
        v = q.pop()
        for u in bwd_link[v]:
            fwd_link[u].remove(v)
            if not fwd_link[u]:
                q.append(u)
    
    q = [v for v, links in enumerate(bwd_link) if not links]
    while q:
        v = q.pop()
        for u in fwd_link[v]:
            bwd_link[u].remove(v)
            if not bwd_link[u]:
                q.append(u)


def bfs(s, fwd_link):
    predecessors = [-1] * n
    q = deque()
    for v in fwd_link[s]:
        predecessors[v] = s
        q.append((v, s))
    visited = set()
    while q:
        v, p = q.popleft()
        if v in visited:
            continue
        visited.add(v)
        predecessors[v] = p

        if v == s:
            break

        for u in fwd_link[v]:
            if u not in visited:
                q.append((u, v))

    circuit = {s}
    v = predecessors[s]
    while v != s:
        circuit.add(v)
        v = predecessors[v]

    return predecessors, circuit


def check(predecessors, circuit, fwd_link):
    for v in circuit:
        fwd_link[v].intersection_update(circuit)
        if len(fwd_link[v]) == 1:
            continue
        for u in fwd_link[v]:
            if predecessors[u] != v:
                return u
    return -1


def print_ans(circuit):
    print(len(circuit))
    print(*(v + 1 for v in circuit))


def solve(fwd_link, bwd_link):
    shave(fwd_link, bwd_link)
    s = -1
    for s, (f, b) in enumerate(zip(fwd_link, bwd_link)):
        if f and b:
            break
    else:
        print(-1)
        return

    while True:
        predecessors, circuit = bfs(s, fwd_link)
        res = check(predecessors, circuit, fwd_link)
        if res == -1:
            print_ans(circuit)
            break
        s = res


n, m = map(int, input().split())
fwd_link = [set() for _ in range(n)]
bwd_link = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    fwd_link[a].add(b)
    bwd_link[b].add(a)

solve(fwd_link, bwd_link)

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)

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 = {}
vs = []
def dfs(i):
    if i in vis:
        if vis[i]:
            del vs[:vs.index(i)]
        return vis[i]
    vis[i] = True
    vs.append(i)
    for j in g[i]:
        if dfs(j):
            return True
    vis[i] = False
    vs.pop()
    return False
for i in range(n):
    if dfs(i):
        break
else:
    print(-1)
    exit()
dist = {v: i for i, v in enumerate(vs)}
vis = set()
ws = []
nxt = 0
for i in vs:
    if dist[i] < nxt:
        continue
    k = -1
    for j in g[i]:
        if j not in dist or dist[j]<dist[i] and j not in vis:
            continue
        if k == -1:
            k = j
            continue
        dj = (dist[j]-dist[i])%len(vs)
        dk = (dist[k]-dist[i])%len(vs) 
        if dj > dk:
            k, j = j, k
    nxt = dist[k]
    vis.add(i)
    ws.append(i)
    if k in vis:
        del ws[:ws.index(k)]
        break
print(len(ws))
for i in ws:
    print(i)

Solution (Python):
def cycle_detection(V, E, s):
    prev = [-1] * len(V)
    stack = [s]
    while stack:
        v = stack.pop()
        for u in E[v]:
            if u == s:
                prev[u] = v
                return (s, prev)
            if prev[u] == -1:
                stack.append(u)
                prev[u] = v
    return (-1, prev)

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

dag = False
for v in range(N):
    s, prev = cycle_detection(V, E, v)
    if s != -1: break
else:
    dag = True

if dag: print(-1)
else:
    
    cycle = set()
    cycle.add(s)
    pv = prev[s]
    while pv != s:
        cycle.add(pv)
        pv = prev[pv]
    
    for a, b in edges:
        if a in cycle and b in cycle and prev[b] != a:
            pv = prev[b]
            while pv != a:
                cycle.remove(pv)
                pv = prev[pv]
            prev[b] = a
    print(len(cycle))
    print(*[v + 1 for v in cycle], sep='\n')

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]

    graph_data = defaultdict(set)
    jisuu_list = [0 for i in range(node_num + 1)]
    for i in range(edge_num):
        a, b = data[i]
        graph_data[a].add(b)
        jisuu_list[b] += 1


    now_set = set()
    next_set = set()
    for i in range(1, node_num + 1):
        if jisuu_list[i] == 0:
            now_set.add(i)

    while len(now_set) > 0:
        for now_node in now_set:
            for next_node in graph_data[now_node]:
                jisuu_list[next_node] -= 1
                if jisuu_list[next_node] == 0:
                    next_set.add(next_node)
        now_set = next_set
        next_set = set()

    if max(jisuu_list) == 0:
        print(-1)
        sys.exit()

    ans = []
    dist = 10 ** 10
    for i in range(1, node_num + 1):
        if jisuu_list[i] == 0:
            continue

        parent_node = [0 for i in range(node_num + 1)]
        now_set = set()
        next_set = set()
        now_set.add(i)
        dist_kari = 0
        fin_flg = 0
        while len(now_set) > 0:
            dist_kari += 1
            
            for now_node in now_set:
                for next_node in graph_data[now_node]:
                    
                    if next_node == i:
                        parent_node[next_node] = now_node
                        fin_flg = 1
                        break
                    if jisuu_list[next_node] == 0:
                        continue
                    if parent_node[next_node] == 0:
                        parent_node[next_node] = now_node
                        next_set.add(next_node)
                if fin_flg:
                    break
            if fin_flg:
                break
            now_set = next_set
            next_set = set()

        if dist_kari < dist and fin_flg:
            dist = dist_kari
            ans = []
            now_node = parent_node[i]
            ans.append(i)
            
            while now_node != i:
                ans.append(now_node)
                now_node = parent_node[now_node]

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







if __name__ == '__main__':
    main()

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
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

from collections import deque

inf = float("inf")
ans = inf
ss = []
def bfs(i):
    global ans, ss
    dist = [inf]*n
    prev = [None]*n
    que = deque()
    
    for to in G[i]:
        que.append(to)
        dist[to] = 1
        prev[to] = i
    while que:
        cur = que.popleft()
        if cur == i:
            break
        for to in G[cur]:
            if dist[to] != inf:
                continue
            dist[to] = dist[cur]+1
            prev[to] = cur
            que.append(to)

    if dist[i] < ans:
        ans = dist[i]
        ss = [i]
        for _ in range(ans-1):
            ss.append(prev[ss[-1]])
        

for i in range(n):
    bfs(i)

if ans == inf:
    print(-1)
else:
    print(0)
    exit()
    print(ans)
    
    for i in reversed(ss):
        print(i+1)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

from collections import deque

inf = float("inf")
ans = inf
ss = []
def bfs(i):
    global ans, ss
    dist = [inf]*n
    prev = [None]*n
    que = deque()
    
    for to in G[i]:
        que.append(to)
        dist[to] = 1
        prev[to] = i
    while que:
        cur = que.popleft()
        if cur == i:
            break
        for to in G[cur]:
            if dist[to] != inf:
                continue
            dist[to] = dist[cur]+1
            prev[to] = cur
            que.append(to)

    if dist[i] < ans:
        ans = dist[i]
        ss = [i]
        for _ in range(ans-1):
            ss.append(prev[ss[-1]])
        

for i in range(n):
    bfs(i)

if ans == inf:
    print(-1)
else:
    print(ans)
    
    for i in reversed(ss):
        print(i+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):

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

def bfs(sv, to_list):
  dist = [INF for i in range(n)]
  hist = [-1 for i in range(n)]
  q = []
  dist[sv] = 0
  q.append(sv)
  while len(q) > 0:
    v = q[0]
    del q[0]
    for j in to_list[v]:
      if dist[j] != INF:
        continue
      hist[j] = v
      dist[j] = dist[v] + 1
      q.append(j)
  min_cycle = INF
  min_hist = -1
  for i in range(n):
    if i == sv:
      continue
    for j in to[i]:
      if j == sv:
        if min_cycle > dist[j]:
          min_cycle = dist[i]
          min_hist = i
  res = []
  temp_v = min_hist
  if min_cycle < INF:
    while temp_v > -1:
      res.append(temp_v)
      temp_v = hist[temp_v]
  else:
    res = [1 for i in range(n+1)]
  return res
    

to = [[] for i in range(m)]
for i in range(m):
  a, b = map(int, input().split())
  to[a-1].append(b-1)
if len(to) == 0:
  print(-1)
else:  
  c = [bfs(i, to) for i in range(n)]
  ans = [1 for i in range(n+1)]
  for i in range(n):
    if len(ans) > len(c[i]):
      ans = c[i]
  if len(ans) == n + 1:
    print(-1)
  else:
    print(len(ans))
    for v in ans[::-1]:
      print(v+1)

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 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, v-1+N, 1)

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):
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):
    
    vs.add(v)
    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:
            pvs.add(v)
            path.append(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
                vs.add(u)
                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

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

edges = [[] for _ in range(N)]
edgesR = [[] for _ in range(N)]

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edgesR[to].append(fr)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    loopStart = L.pop()
    while L[0] != loopStart:
        L.popleft()
    V = set(L)
    dist = [float('inf')] * N
    que = deque([(loopStart, 0)])

    while que:
        now, d = que.popleft()

        if dist[now] <= d:
            if now == loopStart:
                dist[loopStart] = d
                break
            continue
        dist[now] = d

        for to in edges[now]:
            if to in V:
                que.append((to, d + 1))

    ans = [loopStart]
    now = loopStart
    while dist[now] > 1:
        for back in edgesR[now]:
            if dist[now] - 1 == dist[back]:
                ans.append(back)
                now = back
                break

    ans = set([a + 1 for a in ans])
    print(len(ans))
    print(*ans, sep='\n')
    exit()

print(-1)

Solution (Python):
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    loopStart = L.pop()
    while L[0] != loopStart:
        L.popleft()

    ans = []
    K = len(L)
    for i, now in enumerate(L):
        for to in edges[now]:
            if i + 1 >= K or to == L[i + 1]:
                ans.append(now + 1)
                break
        else:
            break
    else:
        print(0)
        print()
        
        
        exit()

print(-1)

Solution (Python):
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    print(0)
    print()
    exit()

    loopStart = L[-1]
    while L[0] != loopStart:
        L.popleft()

    print(len(L) - 1)
    ans = [v + 1 for v in L]
    print(*ans[: -1], sep='\n')
    exit()

print(-1)

Solution (Python):
import queue

import sys
sys.setrecursionlimit(10000)

N, M = map(int, input().split())
S = set(range(N))

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

visit = [0] * N
def DFS(p, n):
    if visit[p] != 0:
        return visit[p]
    else:
        visit[p] = n + 1
        for i in to[p]:
            r = DFS(i, n + 1)
            if r > 0:
                return r
        visit[p] = -1
        return -1

for i in range(N):
    r = DFS(i,0)
    if r > 0:
        for j in range(N):
            if visit[j] < r:
                S.discard(j)
        for j in range(N):
            if j in S:
                for k in to[j]:
                    if k in S:
                        if visit[k] < visit[j]:
                            for l in range(N):
                                if visit[l] < visit[k] or visit[l] > visit[j]:
                                    S.discard(l)
                        else:
                            for l in range(N):
                                if visit[l] > visit[j] and visit[l] < visit[k]:
                                    S.discard(l)
        print(len(S))
        for j in list(S):
            print(j+1)
        break
    if i == N-1:
        print(-1)

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 vs in 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.extend(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[:]