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

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)

L = 10**14
num = -1
for n in range(N):
    q = [n]
    checked = [False]*N
    checked[n] = True
    before = [None]*N
    c = 0
    ok = False
    while q:
        c += 1
        qq = []
        for p in q:
            for np in graph[p]:
                if not checked[np]:
                    before[np] = p
                    qq.append(np)
                    checked[np] = True
                elif np == n:
                    before[np] = p
                    ok = True
                    break
        if ok: break
        q = qq
    
    if ok and c < L:
        L = c
        num = n
        ans = []
        k = n
        for _ in range(c):
            k = before[k]
            ans.append(k+1)

if num == -1:
    print(-1)
else:
    print(len(ans))
    for a in reversed(ans):
        print(a)

Solution (Python):
import sys
sys.setrecursionlimit(100000)

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

R = {}
for a, b in AB:
  if a in R:
    R[a].append(b)
  else:
    R[a] = [b]

def nasu(x, e):
  D[x] = 1
  if x not in R:
    return []
  for i in R[x]:
    if i == e:
      return [i]
    if D[i] == 0:
      t = nasu(i, e)
      if t != []:
        return [i] + t
  return []

for i in range(1, N + 1):
  D = [0] * (N + 1)
  L = nasu(i, i)
  if L != []:
    break
else:
  print(-1)
  exit()

D = [0] * (N + 1)
for i in L:
  D[i] = 1

LEN = len(L)
L = L + L

i = 0
while i < LEN:
  for j in range(i + LEN - 1, i, -1):
    if D[L[j]] != 0 and L[j] in R[L[i]]:
      for k in range(j - 1, i, -1):
        D[L[k]] = 0
      i = j
      break

A = []
for i in range(LEN):
  if D[L[i]] == 1:
    A.append(L[i])

print(len(A))
for i in A:
  print(i)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return [int(i)-1 for i in input().split()]
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n = II()
    ans = 0
    for i in range(1, n + 1):
        ans += i & 1
    print(ans/n)
    return


def B():
    _, k = LI()
    h = LI()
    ans = 0
    for i in h:
        ans += i >= k
    print(ans)
    return


def C():
    n = II()
    a = LI()
    d = defaultdict(int)
    for i in range(n):
        d[a[i] + 1] = i + 1
    for _, v in sorted(d.items()):
        print(v, end=" ")
    print()
    return

def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    """ 6以上の数であれば p (素数) <= n のlistを返す """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]


def D():
    a, b = LI()
    da = defaultdict(int)
    db = defaultdict(int)
    for i in range(2, int(math.sqrt(a)) + 1):
        while a % i == 0:
            a = a // i
            da[i] = 1
        while b % i == 0:
            b = b // i
            db[i] = 1
    da[a] = 1
    db[b] = 1
    da[1] = 1
    db[1] = 1
    print(len(set(da.keys()) & set(db.keys())))
    return


def E():
    n, m = LI()
    dp = [inf] * (1 << n)
    dp[0] = 0
    for _ in range(m):
        a, b = LI()
        c = LI_()
        fulls = sum((1<<c[i] for i in range(b)))
        for i in range(1 << n):
            dp[i | fulls] = min(dp[i | fulls], dp[i] + a)
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])
    return


def F():
    n,m = LI()
    edg = [[] for i in range(n)]
    redg = [[] for i in range(n)]
    
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        redg[b].append(a)

    def dijkstra(start):
        dist = [inf] * n
        dist[start] = 0
        q = [(0,start)]
        while q:
            du, u = heappop(q)
            for i in edg[u]:
                if du + 1 < dist[i]:
                    dist[i] = du + 1
                    heappush(q, (du + 1, i))
        return dist
    
    d = [None] * n
    for i in range(n):
        d[i] = dijkstra(i)

    tmp = inf
    tt = None
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if tmp > d[i][j] + d[j][i]:
                tt = (i, j)
                tmp = d[i][j] + d[j][i]

    if tmp != inf:
        print(tmp)
        s, g = tt
        ans1 = [s]
        ans2 = [g]
        q = deque([s])
        while q:
            a = q.pop()
            for ai in redg[a]:
                if g != ai and d[g][ai] + 1 == d[g][a]:
                    ans1.append(ai)
                    q.append(ai)
                    break
        q = deque([g])
        while q:
            a = q.pop()
            for ai in redg[a]:
                if s != ai and d[s][ai] + 1 == d[s][a]:
                    ans2.append(ai)
                    q.append(ai)
                    break
        ans = ans1 + ans2
        for a in ans:
            print(a+1)

    else:
        print(-1)
    return


if __name__ == '__main__':
    F()

Solution (Python):
import sys
import copy
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
uv = [ set() for _ in range(N)]
vu = [ set() for _ in range(N)]
for _ in range(M):
    A, B = inpl()
    uv[A-1].add(B-1)
    vu[B-1].add(A-1)

EMPTY, LOOP, TREE = 0, 1, 2
ENTER, EXIT = 0, 1
status = [EMPTY] * N
for s in range(N):
    states_pool = [(s,[],ENTER)]
    while states_pool:
        u, chain, flag = states_pool.pop()
        if flag == EXIT or status[u] == TREE:
            status[u] = TREE
            continue
        elif status[u] == LOOP:
            break
        else: 
            status[u] = LOOP
            states_pool.append((u,chain,EXIT))
            new_chain = copy.copy(chain)
            new_chain.append(u)
            for c in uv[u]:
                states_pool.append((c, new_chain, ENTER))
    else:
        continue
    break
else:
    print(-1)
    exit()

n = 0
while chain[n] != u:
    n += 1
chain = chain[n:]
L = len(chain)
nextnode = [None]*N
for i in range(L-1):
    nextnode[chain[i]] = chain[i+1]
nextnode[chain[L-1]] = chain[0]
pos = [None]*N
for p in range(len(chain)):
    pos[chain[p]] = p
i = 0
while i < L:
    h = 1
    c = chain[(i+1)%L]
    for j in uv[chain[i % L]]:
        p = pos[j]
        if p is None:
            continue
        else:
            if (p-i)%L > h:
                h = (p-i)%L
                c = j
    nextnode[chain[i % L]] = c
    i += 1
    while chain[i % L] != c:
        pos[chain[i % L]] = None
        i += 1

loop = [c]
k = c
while nextnode[k] != c:
    k = nextnode[k]
    loop.append(k)
print(len(loop))
for l in loop:
    print(l+1)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
uv = [ set() for _ in range(N)]
vu = [ set() for _ in range(N)]
for _ in range(M):
    A, B = inpl()
    uv[A-1].add(B-1)
    vu[B-1].add(A-1)

EMPTY, LOOP, TREE = 0, 1, 2
ENTER, EXIT = 0, 1
status = [EMPTY] * N
for s in range(N):
    states_pool = [(s,[],ENTER)]
    while states_pool:
        u, chain, flag = states_pool.pop()
        if flag == EXIT or status[u] == TREE:
            status[u] = TREE
            continue
        elif status[u] == LOOP:
            break
        else: 
            status[u] = LOOP
            states_pool.append((u,chain,EXIT))
            new_chain = chain.copy()
            new_chain.append(u)
            for c in uv[u]:
                states_pool.append((c, new_chain, ENTER))
    else:
        continue
    break
else:
    print(-1)
    exit()

n = 0
while chain[n] != u:
    n += 1
chain = chain[n:]
L = len(chain)
nextnode = [None]*N
for i in range(L-1):
    nextnode[chain[i]] = chain[i+1]
nextnode[chain[L-1]] = chain[0]
pos = [None]*N
for p in range(len(chain)):
    pos[chain[p]] = p
i = 0
while i < L:
    h = 1
    c = chain[(i+1)%L]
    for j in uv[chain[i % L]]:
        p = pos[j]
        if p is None:
            continue
        else:
            if (p-i)%L > h:
                h = (p-i)%L
                c = j
    nextnode[chain[i % L]] = c
    i += 1
    while chain[i % L] != c:
        pos[chain[i % L]] = None
        i += 1

loop = [c]
k = c
while nextnode[k] != c:
    k = nextnode[k]
    loop.append(k)
print(len(loop))
for l in loop:
    print(l+1)

Solution (Python):
def find_cycle(N, AB):
  for c in range(N):
    stack = [(c, [])]
    while stack:
      
      curr, visited = stack.pop()
      if curr in visited:
        
        return visited
      else:
        
        for i in AB[curr]:
          stack.append((i, visited+[curr]))
  return False

 
 
def find_smaller_cycle(cycle, AB):
    i = 0
    while i < len(cycle):
        v = cycle[i]
        if AB[v]:
            n = AB[v].pop()
            if n in cycle:
                r = cycle.index(n)
                if i < r:
                    cycle = cycle[:i+1] + cycle[r:]
                else:
                    cycle = cycle[r:i+1]
                i = cycle.index(v)
        else:
            i += 1
            
    return cycle
 
 
N, M = [int(i) for i in input().split()]
 
AB = [[] for _ in range(N)]
for _ in range(M):
    A, B = [int(i) - 1 for i in input().split()]
    AB[A].append(B)

cycle = find_cycle(N, AB)

if not cycle:
    print(-1)
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print(len(cycle))
    for v in cycle:
        print(v + 1)

Solution (Python):
def dfs(N, AB):
  status = [-1] * N
  for i in range(N):
      if status[i] == 1:
          continue
      stack = [i]
      status[i] = 0
      while stack:
          print("stack:", stack)
          v = stack[-1]
          if AB[v]:
              n = AB[v].pop()
              if status[n] == -1:
                  stack.append(n)
                  status[n] = 0
              elif status[n] == 0:
                  idx = stack.index(n)
                  print("stack:", stack, "n:", n, "idx:", idx)
                  cycle = stack[idx:]
                  
                  return cycle
          else:                  
              status[v] = 1
              stack.pop()
 
  return False

def dfs_2(N, AB):
  for c in range(N):
    stack = [(c, [])]
    while stack:
      
      curr, visited = stack.pop()
      if curr in visited:
        
        return visited
      else:
        
        for i in AB[curr]:
          stack.append((i, visited+[curr]))
  return False

 
 
def find_smaller_cycle(cycle, AB):
    i = 0
    while i < len(cycle):
        v = cycle[i]
        if AB[v]:
            n = AB[v].pop()
            if n in cycle:
                r = cycle.index(n)
                if i < r:
                    cycle = cycle[:i+1] + cycle[r:]
                else:
                    cycle = cycle[r:i+1]
                i = cycle.index(v)
        else:
            i += 1
            
    return cycle
 
 
N, M = [int(i) for i in input().split()]
 
AB = [[] for _ in range(N)]
for _ in range(M):
    A, B = [int(i) - 1 for i in input().split()]
    AB[A].append(B)




cycle = dfs_2(N, AB)

if not cycle:
    print(-1)
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print(len(cycle))
    for v in cycle:
        print(v + 1)

Solution (Python):

import sys
from collections import deque

N,M=map(int, raw_input().split())
al=[ [] for i in range(N+1) ]
edge=[]

for i in range(M):
	a,b=map(int, sys.stdin.readline().split())
	al[a].append(b)
	edge.append((a,b))


def bfs(start,end):
	Visit=[ 0 for _ in range(N+1) ]	
	d=[ float("inf") for _ in range(N+1)]	
	prev=[ None for _ in range(N+1)]	
	d[start]=0
	q=deque()
	q.append(start)
	Visit[start]=1

	while q:
		fro=q.popleft()
		for to in al[fro]:
			if Visit[to]==0:
				Visit[to]=1
				alt=d[fro]+1
				if alt<d[to]:
					d[to]=alt
					prev[to]=fro
				q.append(to)
	return d[end],prev


K=float("inf")
v=[]
start=None
end=None

for x,y in edge:
	kyori,keiro=bfs(y,x)
	if kyori<K:
		K=kyori+1
		v=keiro
		start=y
		end=x

if K==float("inf"):
	print -1
else:
	print K
	print end
	fro=end
	while fro!=start:
		fro=v[fro]
		print fro

Solution (Python):
n, m = map(int, input().split())
edges = [[] for _ in range(n)]

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


def get_first_cycle(n, edges):
    seen = [-1] * n  
    for start in range(n):
        if seen[start] == 0:
            continue
        seen[start] = 1
        path = [start]
        while path:
            now = path[-1]
            if not edges[now]:
                path.pop()
                seen[now] = 0
                continue

            next_node = edges[now].pop()
            if seen[next_node] == -1:
                path.append(next_node)
                seen[next_node] = 1

            elif seen[next_node] == 1:
                idx = path.index(next_node)
                cycle = path[idx:]
                return cycle
    return False


cycle = get_first_cycle(n, edges)
if not cycle:
    print(-1)
    exit()

nodes = set(cycle)
length = len(cycle)
i = 0
while i < length:
    now = cycle[i]
    routes = edges[now]
    while routes:
        to = routes.pop()
        if to in nodes:
            update = True
            idx = cycle.index(to)
            cycle = cycle[:i+1] + cycle[idx:]
            nodes = set(cycle)
            length = len(cycle)
            break
    i += 1

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

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
edge = [[] for _ in range(n)]
for _ in range(m):
    a,b = LI()
    edge[a-1].append(b-1)

visited = [False]*n
def dfs(s):
    if visited[s]:
        return True
    visited[s] = True
    for i in edge[s]:
        if dfs(i):
            return True
    visited[s] = False
    return False

for i in range(n):
    if dfs(i):
        print(0)
        break
else:
    print(-1)

Solution (Python):
from collections import*
n,m,*t=map(int,open(0).read().split())
i=[0]*n
o=[[]for _ in i]
for a,b in zip(*[iter(t)]*2):
  o[a-1]+=b-1,
  i[b-1]+=1
q,r=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):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        a,b=map(lambda x:int(x)-1,input().split())
        E[a].append(b)
    
    def bfs(sv):
        prev=[-1]*n
        flag=False
        from collections import deque
        Q=deque([sv])
        while(Q):
            v=Q.popleft()
            for nv in E[v]:
                if(nv==sv):
                    break 
                elif(prev[nv]==-1):
                    prev[nv]=v
                    Q.append(nv)
            else:
                continue
            break 
        else:
            return [0]*(n+1)
        loop=[]
        while(v!=-1):
            loop.append(v)
            v=prev[v]
        loop.reverse()
        return loop
    
    ans=[0]*(n+1)
    for i in range(n):
        loop=bfs(i)
        if(len(loop)<len(ans)):
            ans=loop
    if(len(ans)==n+1):
        print(-1)
    else:
        print(len(ans))
        for v in ans: print(v+1)
resolve()

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

    
    def bfs(sv):
        prev=[-1]*n
        flag=False
        from collections import deque
        Q=deque([sv])
        while(Q):
            v=Q.popleft()
            for nv in E[v]:
                if(nv==sv):
                    flag=True
                    break
                elif(prev[nv]==-1):
                    prev[nv]=v
                    Q.append(nv)
            if(flag): break
        if(not flag):
            return [0]*(n+1)
        else:
            loop=[]
            while(v!=-1):
                loop.append(v)
                v=prev[v]
            loop.reverse()
            return loop

    
    ans=[0]*(n+1)
    for i in range(n):
        loop=bfs(i)
        if(len(loop)<len(ans)):
            ans=loop
    if(len(ans)==n+1):
        print(-1)
    else:
        print(len(ans))
        for v in ans: print(v+1)
resolve()

Solution (Python):

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    A[i], B[i] = map(int, input().split())



C = [[]] * N
for a in A:
    C[a-1] = [b-1 for i, b in enumerate(B) if A[i] == a]


search_stack = [[]] * N
visited = [[]] * N
next_position = [-1] * N

for i in range(N):
    search_stack[i] = [i]
    visited[i] = []
    while search_stack[i] != []:
        next_position[i] = search_stack[i].pop(0)
        visited[i].append(next_position[i])
        for node in C[next_position[i]]:
            if node == i:
                visited[i].append(node)
                search_stack[i] = []
                break
            elif node in visited[i]:
                continue
            elif node in search_stack[i]:
                continue
            elif C[node] == []:
                continue
            else:
                search_stack[i].append(node)

short = None
for v in visited:
    if len(v) >= 2 and v[0] == v[-1]:
        if not short or len(v) < len(short):
            short = v


if short:
    del short[-1]
    print(len(short))
    for s in short:
        print(s+1)
else:
    print(-1)

Solution (Python):
def dfs(N, AB):
    status = [-1] * N
    for i in range(N):
        if status[i] == 1:
            continue
        stack = [i]
        status[i] = 0
        while stack:
            v = stack[-1]
            if AB[v]:
                n = AB[v].pop()
                if status[n] == -1:
                    stack.append(n)
                    status[n] = 0
                elif status[n] == 0:
                    idx = stack.index(n)
                    cycle = stack[idx:]
                    
                    return cycle
            else:                  
                status[v] = 1
                stack.pop()

    return False


def find_smaller_cycle(cycle, AB):
    i = 0
    while i < len(cycle):
        v = cycle[i]
        if AB[v]:
            n = AB[v].pop()
            if n in cycle:
                r = cycle.index(n)
                if i < r:
                    cycle = cycle[:i+1] + cycle[r:]
                else:
                    cycle = cycle[r:i+1]
                i = cycle.index(v)
        else:
            i += 1
            
    return cycle


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

AB = [[] for _ in range(N)]
for _ in range(M):
    A, B = [int(i) - 1 for i in input().split()]
    AB[A].append(B)
                      
cycle = dfs(N, AB)
if not cycle:
    print(-1)
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print(len(cycle))
    for v in cycle:
        print(v + 1)

Solution (Python):
from collections import deque

     
def dfs(N, AB):
    status = [-1] * N
    for i in range(N):
        if status[i] == 1:
            continue
        stack = [i]
        status[i] = 0
        while stack:
            v = stack[-1]
            if AB[v]:
                n = AB[v].popleft()
                if status[n] == -1:
                    stack.append(n)
                    status[n] = 0
                else:
                    if n in stack:
                        idx = stack.index(n)
                        cycle = stack[idx:]
                        return cycle
            else:                  
                status[v] = 1
                stack.pop()
    return False


def find_smaller_cycle(cycle, AB):
    i = 0
    while i < len(cycle):
        v = cycle[i]
        if AB[v]:
            n = AB[v].popleft()
            if n in cycle:
                r = cycle.index(n)
                if i < r:
                    cycle = cycle[:i+1] + cycle[r:]
                else:
                    cycle = cycle[r:i+1]
                i = cycle.index(v)
        else:
            i += 1
            
    return cycle


N, M = [int(i) for i in input().split()]
AB = [deque() for _ in range(N)]
for _ in range(M):
    A, B = [int(i) - 1 for i in input().split()]
    AB[A].append(B)
                      
cycle = dfs(N, AB)
if not cycle:
    print(-1)
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print(len(cycle))
    for v in cycle:
        print(v + 1)

Solution (Python):
from collections import deque

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

def bfs(i) :
    dist = [float('inf')] * N
    pre = [-1] * N
    
    queue = deque([(i, 0)])
    while queue :
        cur, cost = queue.popleft()
        if dist[cur] < cost :
            continue
        for nex in v[cur] :                
            if cost + 1 < dist[nex] :
                dist[nex] = cost + 1
                pre[nex] = cur
                queue.append((nex, cost + 1))
    
    return dist[i], pre

mi = -1
mv = float('inf')
mp = []
for i in range(N) :
    m, pre = bfs(i)
    if m < mv :
        mi, mv, mp = i, m, pre

if mi >= 0 :
    print(mv)
    cur = mi
    while mp[cur] != mi :
        print(cur + 1)
        cur = mp[cur]
    print(cur + 1)
else :
    print(-1)

Solution (Python):

"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
import heapq


def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   

def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    

"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())


dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')


ABT = zip(A, B, totAB)
result = 0

sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)


(x >> i) & 1


dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break

add = 1 
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)


li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    


org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)




    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""



def bfs(n):
    clsd = set()
    opnd = collections.deque()        
    root = [None]*N
    d_list = [0]*N
    opnd.append(n)
    
    
    while len(opnd) != 0:

        
        
        
        now = opnd.popleft()
        clsd.add(now)
        
        for e in E[now]:
            if e in clsd:
                if e == n:
                    res = [now]
                    
                    
                    dist = d_list[now] + 1
                    while len(res) != dist:
                        
                        res.append(root[res[-1]])
                    return [list(reversed(res)), dist]
                
            else:
                opnd.append(e)
                root[e] = now
                d_list[e] = d_list[root[e]]+1
    return [[], inf] 


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

E = [[] for n in range(N)]

 
for m in range(M):
    e = list(map(int, input().split()))
    E[e[0]-1].append(e[1]-1)

inf = 10**9

    
def main(): 
    res = []
    d_min = inf
    for n in range(N):
        graph, dist = bfs(n)
        if dist < d_min:
            d_min = dist
            res = graph
    if d_min != inf:
       print(d_min)
       for n in range(d_min):
           print(res[n]+1)
    else:
       print(-1)
        
                
            
            
                

    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
def serp(s):
  prev = [-1]*n
  q=deque([s])
  while q:
    v = q.pop()
    for nv in e[v]:
      if nv==s: prev[nv]=v; return(s,prev)
      if prev[nv]<0: q+=nv,; prev[nv] =v
  return(-1,prev)
n,m,*t=map(int,open(0).read().split())
e,ab = [[] for i in range(n)],[]
for a,b in zip(*[iter(t)]*2):
  e[a-1]+= b-1,
  ab += [(a-1,b-1)]
for v in range(n):
  v0,prev = serp(v)
  if v0>=0: break
if v0<0: print(-1); sys.exit()
c=set()
c.add(v0)
pv = prev[v0]
while pv!=v0:
  c.add(pv)
  pv=prev[pv]
for a,b in ab:
  if a in c and b in c and prev[b]!=a:
    pv = prev[b]
    while pv !=a:
      c.remove(pv)
      pv=prev[pv]
    prev[b]=a
print(len(c))
for i in c: print(i+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):
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 []


tmp = 0
ans = 10 ** 10
tmpp = []
p = []
vs = [0] * 1005


def dfs2(x):
    global ans, p, tmp, tmpp
    if len(p) >= ans:
        return
    p.append(x)
    for v in g[x]:
        if v == tmp:
            ans = len(p)
            tmpp = p[:]
            continue
        if not vs[v]:
            vs[v] = 1
            dfs2(v)
    p.pop()


a = []
for i in range(1, 1 + n):
    tmp = i
    p = []
    vs = [0] * 1005
    dfs2(i)
    if len(tmpp) == ans:
        a = tmpp[:]

if not len(a):
    print(-1)
    exit(0)

print(len(a))
for i in a:
    print(i)