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






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,M = IL()
graph = {i:[] for i in range(N)}
for _ in range(M):
  a,b = IL()
  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)

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

def find_cycle(adj, start = 0):
    """
    有効グラフ上で、0-indexedが前提の実装。
    あれば、適当なサイクルをリストで返す。
    参考1: https://qiita.com/drken/items/a803d4fc4a727e02f7ba
    参考2: https://qiita.com/Kiri8128/items/2b0023bed9af642c751c
    """
    global arrived, finished
    stack = [~start, start]
    history = []
    while stack:
        v = stack.pop()
        if v >= 0:
            arrived[v] = True
            history.append(v)
            for nv in adj[v]:
                if not arrived[nv]:
                    stack.append(~nv)
                    stack.append(nv)
                elif not finished[nv]: 
                    index = history.index(nv)
                    return history[index:]
        else:
            finished[~v] = True
            history.pop()
    return []

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


arrived = [False] * N
finished = [False] * N
while False in arrived:
    start = arrived.index(False)
    cycle = find_cycle(adj, start)
    if cycle:
        break

if not cycle:
    print(-1)
    exit()
else:
    cycle_updated = True
    while cycle_updated:
        cycle_updated = False
        cycle_index = {v:i for i, v in enumerate(cycle)}
        l = len(cycle)
        for i, v in enumerate(cycle):
            cv = cycle[i+1-l]
            for nv in adj[v]:
                if nv != cv and nv in cycle_index:
                    cycle_updated = True
                    j = cycle_index[nv]
                    if i < j:
                        cycle = cycle[:i+1] + cycle[j:]
                    else:
                        cycle = cycle[j:i+1]
                    break
            if cycle_updated:
                break
    print(len(cycle))
    print(*[elem+1 for elem in cycle], sep = '\n')

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,m = map(int, input().split())
ns = defaultdict(set)
es = set()
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    es.add((u,v))



seen = [False] * n
done = [False] * n
hist = []
def dfs(u, pos):
    
    seen[u] = True
    hist.append(u)
    for v in ns[u]:
        if done[v]:
            continue
        elif seen[v]:
            
            pos = v
            return pos
        else:
            pos = dfs(v, pos)
            if pos>=0:
                return pos
    done[u] = True
    hist.pop()
    return pos


def cycle(hist, pos):
    for i, u in enumerate(hist):
        if u==pos:
            break
    return hist[i:]

def sub(hist):
    s = set(hist)
    ss = set((hist[i],hist[i+1]) for i in range(len(hist)-1))
    ss.add((hist[len(hist)-1], hist[0]))
    l = None
    for u,v in es:
        if u in s and v in s and (u,v) not in ss:
            l = []
            for i,k in enumerate(hist):
                if k==v:
                    break
            for j in range(i,len(hist)):
                l.append(hist[j])
                if hist[j]==u:
                    break
            else:
                for j in range(len(hist)):
                    l.append(hist[j])
                    if hist[j]==u:
                        break

    if l is None or len(l)==len(hist):
        return hist
    else:
        return sub(l)
ans = None
for u in range(n):
    pos = dfs(u, -1)
    if pos>=0:
        hist = cycle(hist, pos)
        ans = sub(hist)
        break
if ans is None:
    print(-1)
else:
    print(len(ans))
    write("\n".join(map(lambda x: str(x+1), ans)))

Solution (Python):
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
c=[[] for i in range(N)]
for a,b in AB:
    c[a-1].append(b-1)
from collections import deque
import sys
sys.setrecursionlimit(10**9)
def f2(q):
    s=set(q)
    for a,b in AB:
        if a in s and b in s:
            i=q.index(b)
            if q[i-1]!=a:
                break
    if a in s and b in s and q[i-1]!=a:
        q2=deque([a,b])
        while q[(i+1)%len(q)]!=a:
            q2.append(q[(i+1)%len(q)])
            i+=1
        f2(q2)
    print(len(q),*q,sep='\n')
    exit()
v=[0]*N 
w=[0]*N
def f(p,v,q):
    v[p]=1
    w[p]=1
    q.append(p+1)
    for n in c[p]:
        if v[n]:
            f2(q)
        else:
            f(n,v,q)
    q.pop()
    v[p]=0
for p in range(N):
    if w[p]==0:
        f(p,v,deque())
print(-1)

Solution (Python):
from collections import defaultdict
import heapq


def main():
    N, M = list(map(int, input().split()))
    adj = defaultdict(list)
    for _ in range(M):
        A, B = list(map(lambda x: int(x) - 1, input().split()))
        adj[A].append(B)
    
    min_cycle_size = N + 1
    min_cycle = list()
    for s in range(N):
        parent = [None] * N
        que = [(0, s)]
        while len(que) > 0:
            dist, node = heapq.heappop(que)
            if dist > 0 and node == s:
                break
            for next_node in adj[node]:
                if parent[next_node] is not None:
                    continue
                parent[next_node] = node
                heapq.heappush(que, (dist + 1, next_node))
        
        if parent[s] is not None:
            cycle = [s]
            node = parent[s]
            while node != s:
                cycle.append(node)
                node = parent[node]
            if len(cycle) < min_cycle_size:
                min_cycle_size = len(cycle)
                min_cycle = cycle
    
    if min_cycle_size > N:
        print(-1)
    else:
        print(min_cycle_size)
        for node in min_cycle:
            print(node + 1)


if __name__ == '__main__':
    main()

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

def solve(G, p, ans, st, fst, arr, x):
    arr[p] = x
    cnt_1 = 0
    z = -1
    for nxt in G[p]:
        if nxt in st:
            cnt_1 += 1
            z = nxt
    cnt_2 = 0
    for v in st:
        if p in G[v]:
            cnt_2 += 1
    if cnt_1 > 1 or cnt_2 > 1:
        return False
    elif cnt_1 == 1 and cnt_2 == 1:
        if fst in G[p]:
            for v in st:
                ans.append(v)
            return True
        else:
            k = arr[z]
            for v in st:
                if arr[v] >= k:
                    ans.append(v)
            return True
    for nxt in G[p]:
        st.add(nxt)
        if solve(G, nxt, ans, st, fst, arr, x+1):
            return True
        st.remove(nxt)
    arr[p] = 0
    return False

def main():
    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)
    ans = []
    f = False
    st = set()
    arr = [0]*(n+1)
    for i in range(1, n+1):
        st.add(i)
        if solve(G, i, ans, st, i, arr, 1):
            f = True
            break
        st.remove(i)
    if f:
        print(len(ans))
        ans.sort()
        for v in ans:
            print(v)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Solution (Python):

import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,M=map(int,input().split())
edge=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int1,input().split())
    edge[a].append(b)

used=[False]*N
for i in range(N):
    if used[i]==True:
        continue
    stack=[i]
    path=[]
    while stack:
        v=stack.pop()
        if v>=0:
            used[v]=True
            path.append(v)
            for nv in edge[v]:
                if not used[nv]:
                    stack.append(~v)
                    stack.append(nv)
                else:
                    if nv in path:
                        path.append(nv)
                        break
            else:
                continue
            break
        else:
            path.pop()
    else:
        continue
    break
else:
    print(-1)
    exit()
cycle=path[path.index(path[-1]):]
while True:
    s=set(cycle)
    next_cycle=[]
    for i,v in enumerate(cycle[:-1]):
        next_cycle.append(v)
        for nv in edge[v]:
            if nv==cycle[i+1]:
                continue
            if nv in s:
                next_cycle.extend(cycle[cycle.index(nv):])
                break
        else:
            continue
        break
    else:
        break
    cycle=[]
    ss=set()
    for v in next_cycle:
        if v in ss:
            vv=v
            break
        ss.add(v)
    f=False
    for v in next_cycle:
        if v==vv:
            cycle.append(v)
            if not f:
                f=True
            else:
                break
        elif f:
            cycle.append(v)
    
print(len(cycle)-1)
for v in cycle[:-1]:
    print(v+1)

Solution (Python):
from collections import deque

INF = 10**18
N, M = map(int, input().split())

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

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

loopsize = INF

for root in range(N):
    queue = deque([root])
    dist = [INF for _ in range(N)]
    dist[root] = 0
    prev = [None for _ in range(N)]
    while queue:
        node = queue.popleft()
        for adj in graph[node]:
            if adj == root:
                dist[root] = dist[node] + 1
                prev[root] = node
                break
            if dist[adj] != INF:
                continue
            dist[adj] = dist[node] + 1
            prev[adj] = node
            queue.append(adj)
        else:
            continue
        break
    else:
        continue
    if loopsize > dist[root]:
        loopsize = dist[root]
        path = [root]
        node = root
        while prev[node] != root:
            node = prev[node]
            path.append(node)

if loopsize != INF:
    print(loopsize)
    for node in path:
        print(node + 1)
else:
    print(-1)

Solution (Python):
from collections import deque

class Graph(): 
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append(e[1] - indexed)

INF = 10**18

N, M = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]

g = Graph(N, edge)

loopsize = INF

for i in range(N):
    root = i
    queue = deque([root])
    dist = [INF for _ in range(N)]
    dist[root] = 0
    prev = [None for _ in range(N)]
    while queue:
        node = queue.popleft()
        for adj in g.graph[node]:
            if adj == root: 
                dist[root] = dist[node] + 1
                prev[root] = node
                break
            if dist[adj] != INF:
                continue
            dist[adj] = dist[node] + 1
            prev[adj] = node
            queue.append(adj)
        else:
            continue
        break
    else:
        continue
    
    if loopsize > dist[root]:
        loopsize = dist[root]
        path = [root]
        node = root
        while prev[node] != root:
            node = prev[node]
            path.append(node)

if loopsize != INF:
    print(loopsize)
    for node in path:
        print(node + 1)
else:
    print(-1)

Solution (Python):
from collections import deque

class Graph(): 
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append(e[1] - indexed)

INF = 10**18

N, M = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]

g = Graph(N, edge)

loopsize = INF

for i in range(N):
    root = i
    stack = [root]
    visited = [0 for _ in range(N)]
    visited[root] = 1
    while stack:
        node = stack.pop()
        for adj in g.graph[node]:
            if adj == root: 
                break
            if visited[adj]:
                continue
            visited[adj] = 1
            stack.append(adj)
        else:
            continue
        break
    else:
        continue
    
    queue = deque([root])
    dist = [INF for _ in range(N)]
    dist[root] = 0
    prev = [None for _ in range(N)]
    while queue:
        node = queue.popleft()
        for adj in g.graph[node]:
            if adj == root:
                dist[root] = dist[node] + 1
                prev[root] = node
                break
            if dist[adj] != INF:
                continue
            dist[adj] = dist[node] + 1
            prev[adj] = node
            queue.append(adj)
        else:
            continue
        break
    
    if loopsize > dist[root]:
        loopsize = dist[root]
        path = [root]
        node = root
        while prev[node] != root:
            node = prev[node]
            path.append(node)
        res = path

if loopsize != INF:
    print(loopsize)
    for node in res:
        print(node + 1)
else:
    print(-1)

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 6)
from collections import deque
input = sys.stdin.buffer.readline
INF = float("inf")

def main():
    N,M = map(int,input().split())
    G = [[] for _ in range(N)]
    AB = [tuple(map(int,input().split())) for _ in range(M)]
    for a,b in AB:
        G[a-1].append(b-1)

    Ans = [1]*(N+1)
    
    
    for s in range(N):
        prev = [-1]*N
        dist = [-1]*N
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for nv in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    prev[nv] = v
                    dq.append(nv)
                
                if dist[nv] == 0 and prev[nv] == -1:
                    prev[nv] = v

        
        if prev[s] != -1:
            v = prev[s]
            ans = set()
            for _ in range(max(dist)+1):
                ans.add(prev[v])
                v = prev[v]
            if len(Ans) > len(ans):
                Ans = list(ans)
    
    if len(Ans) == N+1:
        print(-1)
    else:
        print(len(Ans))
        Ans.sort()
        for v in Ans:
            print(v+1)

if __name__ == "__main__":
    main()

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 6)
from collections import deque
input = sys.stdin.buffer.readline
INF = float("inf")

def main():
    N,M = map(int,input().split())
    G = [[] for _ in range(N)]
    AB = [tuple(map(int,input().split())) for _ in range(M)]
    for a,b in AB:
        G[a-1].append(b-1)

    Ans = [1]*(N+1)
    
    
    for s in range(N):
        prev = [-1]*N
        dist = [-1]*N
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for nv in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    prev[nv] = v
                    dq.append(nv)
                
                if dist[nv] == 0:
                    prev[nv] = v

        
        if prev[s] != -1:
            v = prev[s]
            ans = set()
            for _ in range(max(dist)+1):
                ans.add(prev[v])
                v = prev[v]
            if len(Ans) > len(ans):
                Ans = list(ans)
    
    if len(Ans) == N+1:
        print(-1)
    else:
        print(len(Ans))
        Ans.sort()
        for v in Ans:
            print(v+1)

if __name__ == "__main__":
    main()

Solution (Python):
import heapq


class Edge():

    def __init__(self, _to, _cost):
        self.to = _to
        self.cost = _cost


class Dijkstra():
    def __init__(self, V):

        self.G = [[] for i in range(V+1)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        """ 辺数 """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        self.G[_from].append(Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):

        que = []
        heapq.heapify(que)
        d = [10**10] * (self._V+1)
        par = [-1] * (self._V + 1)
        d[s] = 0
        heapq.heappush(que, (0, s))

        while que:
            cost, v = heapq.heappop(que)
            if d[v] < cost:
                continue

            for e in self.G[v]:
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    par[e.to] = v
                    heapq.heappush(que, (d[e.to], e.to))
        return d, par


N, M = map(int, input().split())
G = []
ans = []
now_dis = 10**6
for i in range(M):
    a, b = map(int, input().split())
    G.append((a, b))
for i in range(M):
    graph = Dijkstra(N)
    for j in range(M):
        if j != i:
            graph.add(G[j][0], G[j][1], 1)
    S, T = G[i][0], G[i][1]
    d, par = graph.shortest_path(T)
    if d[S]+1 < now_dis:
        now_dis = d[S]+1
        sub = []
        node = S
        while node != T:
            sub.append(node)
            node = par[node]
        sub.append(T)
        ans = sub

K=len(ans)
if K==0:
    print(-1)
    exit()
print(K)
for x in ans:
    print(x)

Solution (Python):
import sys
from collections import deque


def solve():
    N, M = map(int, input().split())
    edges = [set() for _ in range(N+1)]
    for a, b in (map(int, line.split()) for line in sys.stdin):
        edges[a].add(b)

    
    for start in range(1, N+1):
        visited = [0]*(N+1)

        dq = deque([(start, {start})])
        visited[start] = 1

        while dq:
            
            v, route = dq.popleft()
            
            s = route & edges[v]
            
            if not (not s or s == {start}):
                continue
            for dest in edges[v]:
                
                if dest == start:
                    print(len(route))
                    print(*route, sep='\n')
                    exit()
                
                if visited[dest]:
                    continue
                visited[dest] = 1
                
                dq.append((dest, route | {dest}))

    print(-1)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from collections import deque




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

    
    for start in range(N):
        visited = [0]*N
        Q = deque([(start, {start})])
        append, popleft = Q.append, Q.popleft
        visited[start] = 1

        while Q:
            v, route = popleft()
            
            s = route & E[v]
            
            
            
            if s and s != {start}:
                continue
            for dest in E[v]:
                if dest == start:
                    print(len(route))
                    print(*[n+1 for n in route], sep="\n")
                    return
                if visited[dest]:
                    continue
                visited[dest] = 1
                append((dest, route | {dest}))
    print(-1)
    return


if __name__ == '__main__':
    main()

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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque


def find_shortest_cycle(G, s):
    dq = deque()
    N = len(G)
    INF = float('inf')
    dist = [INF] * N
    dist[s] = 0
    parent = [-1] * N

    ans_last = None 
    dq.append(s)
    
    while dq and ans_last is None:
        v = dq.popleft()
        d = dist[v]
        for n in G[v]:
            
            if dist[n] == 0:
                ans_last = v
                parent[n] = v
                break
            
            elif dist[n] == INF:
                dist[n] = d + 1
                parent[n] = v
                dq.append(n)

    
    if ans_last:
        
        g = ans_last
        route = [g]
        while g != s:
            g = parent[g]
            route.append(g)
        return list(reversed(route))
    
    
    return None

def main():
    N, M, *A = map(int, read().split())

    G = [[] for i in range(N+1)]
    for a, b in zip(A[::2], A[1::2]):
        G[a].append(b)

    
    

    
    
    

    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    min_route = None
    for s in range(1, N+1):
        
        route = find_shortest_cycle(G, s)
        
        if route:
            if min_route is None or len(route) < len(min_route):
                min_route = route
    
    if min_route:
        print(len(min_route), *min_route, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

def shorten_cycle(G, route):
    
    
    

    _next = {k: v for k, v in zip(route, route[1:]+route[:1])}
    v = route[0]
    while True:
        
        for n in G[v]:
            
            
            if n in route and n != _next[v]:
                new_route = [n]
                s = n
                while s != v:
                    s = _next[s]
                    new_route.append(s)
                _next[v] = n
                
                route = new_route
                v = route[0]
                break
        
        else:
            
            v = _next[v]
            if v == route[0]:
                break
    
    return route

def find_cycle(G, s):
    dq = deque()
    N = len(G)
    INF = float('inf')
    dist = [INF] * N
    dist[s] = 0
    parent = [-1] * N

    ans_last = None 
    dq.append(s)
    
    while dq and ans_last is None:
        v = dq.popleft()
        d = dist[v]
        for n in G[v]:
            
            if dist[n] == 0:
                ans_last = v
                parent[n] = v
                break
            
            elif dist[n] == INF:
                dist[n] = d + 1
                parent[n] = v
                dq.append(n)

    
    if ans_last:
        
        g = ans_last
        route = [g]
        while g != s:
            g = parent[g]
            route.append(g)
        return list(reversed(route))
    
    
    return None

def main():
    N, M, *A = map(int, read().split())

    G = [[] for i in range(N+1)]
    for a, b in zip(A[::2], A[1::2]):
        G[a].append(b)

    
    

    
    
    

    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    min_route = None
    for s in range(1, N+1):
        
        route = find_cycle(G, s)
        
        if route:
            min_route = shorten_cycle(G, route)
            break
    
    if min_route:
        print(len(min_route), *min_route, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

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)