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

ret = [0] * (n + 1)
for start in range(n):
    parent = [-1] * n
    q = [start]
    while len(q) > 0:
        i = q.pop(0)
        for j in edges[i]:
            if j == start:
                loop = [i]
                while i != start:
                    i = parent[i]
                    loop.append(i)
                if len(ret) > len(loop):
                    ret = loop
                break
            if parent[j] == -1:
                parent[j] = i
                q.append(j)

if len(ret) > n:
    print(-1)
else:
    print(len(ret))
    for i in reversed(ret):
        print(i + 1)

Solution (Python):
n,m = map(int, input().split())
link = [[] for _ in range(n)]
ab=[]
for i in range(m):
    a,b = list(map(int,input().split()))
    ab.append([a,b])
    link[a-1].append(b-1)

from collections import deque
def best_cycle(a,b):
    a,b=itm
    a-=1
    b-=1
    Q = deque()
    Q.append([b,[b]])
    visited=[-1]*n
    visited[b]=1

    while Q:
        now,path = Q.popleft()
        for nxt in link[now]:
            if nxt==a: 
                return True,path + [nxt]
            if visited[nxt]!=-1:
                continue
            visited[nxt]=1
            Q.append([nxt,path + [nxt]])
    return False,[]

mn = 10**10
ans=[]
found=False

for itm in ab:
    a,b = itm
    ret,path = best_cycle(a,b)
    if ret and len(path) < mn:
        ans=path
        mn = len(path)
        found=True

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

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


def solve():
    N, M = map(int, input().split())
    d = {i:[] for i in range(1, N+1)}
    l = []
    INF = 10**12
    v = INF

    for _ in range(M):
        A, B = map(int, input().split())
        d[A].append(B)
        l.append((A, B))

    ans = []
    for i, j in l:
        INF = 10**12
        dist = [-1]*(N+1)
        prev = [-1]*(N+1)
        dist[j] = 0
        prev[j] = 0
        q = deque([j])

        while q:
            a = q.popleft()
            for b in d[a]:
                if dist[b]==-1:
                    dist[b] = dist[a]+1
                    prev[b] = a
                    q.append(b)

        if v>dist[i]+1 and dist[i]!=-1:
            v = dist[i]+1
            buf = i
            ans = []
            while buf:
                ans.append(buf)
                buf = prev[buf]

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


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque

N, M = map(int, input().split())
d = {i:[] for i in range(1, N+1)}
l = []
INF = 10**12
v = INF

for _ in range(M):
    A, B = map(int, input().split())
    d[A].append(B)
    l.append((A, B))

ans = []
for i, j in l:
    INF = 10**12
    dist = [-1]*(N+1)
    prev = [-1]*(N+1)
    dist[j] = 0
    prev[j] = 0
    q = deque([j])

    while q:
        a = q.popleft()
        for b in d[a]:
            if dist[b]==-1:
                dist[b] = dist[a]+1
                prev[b] = a
                q.append(b)

    if v>dist[i]+1 and dist[i]!=-1:
        v = dist[i]+1
        buf = i
        ans = []
        while buf!=0:
            ans.append(buf)
            buf = prev[buf]

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

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from collections import deque,defaultdict,Counter
def main():
    N,M = map(int,input().split())
    G = [[] for _ in range(N)]
    G_rev = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G_rev[b].append(a)
    
    s,g = None,None
    ans = INF
    q = deque([])
    for i in range(N):
        q.append(i)
        dist = [-1] * N
        dist[i] = 0
        while q:
            v = q.popleft()
            for e in G[v]:
                if i == e:
                    if ans > dist[v] + 1:
                        ans = dist[v] + 1
                        s,g = i,v
                elif dist[e] < 0:
                    dist[e] = dist[v] + 1
                    q.append(e)

    if ans == INF:
        print(-1)
    else:
        print(ans)
        q.append(s)
        dist = [-1] * N
        dist[s] = 0
        while q:
            v = q.popleft()
            for e in G[v]:
                if e == g:
                    dist[g] = dist[v] + 1
                    q.clear()
                    break
                elif dist[e] < 0:
                    dist[e] = dist[v] + 1
                    q.append(e)
        route = [g + 1]
        now = g
        while now != s:
            for e in G_rev[now]:
                if dist[e] == dist[now] - 1:
                    now = e
                    break
            route.append(now + 1)
        print('\n'.join(map(str,route)))
if __name__ == '__main__':
    main()

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))


N, M = LI()
AB = [LI() for _ in range(M)]


link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N


def joint(v, visit):
    if impossible[v]:
        return None
    visit = visit + [v]
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if t is not None:
            return t
    impossible[v] = True
    return None


def solve(l):
    n = len(l)
    d = {l[i]: i for i in range(n)}
    for i in range(n):
        x = l[i]
        for y in link[x]:
            if y in d:
                j = d[y]
                if (i + 1) % n == j:
                    continue
                if j < i:
                    l = l[j : i + 1]
                else:
                    l = l[: i + 1] + l[j:]
                return solve(l)
    return l
            

def main():
    t = None
    for i in range(N):
        t = joint(i, [])
        if t is not None:
            break
    if t is None:
        print(-1)
        return
    
    ans = solve(t)
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
import sys

input = sys.stdin.buffer.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
infi = 10 ** 10


def bfs(start):
    
    res = (infi, -1)
    dist = [-1] * (n + 1)
    par = [-1] * (n + 1)
    que = deque([])
    que.append(start)
    dist[start] = 0
    while que:
        v = que.popleft()
        for u in graph[v]:
            if dist[u] >= 0:
                continue
            dist[u] = dist[v] + 1
            par[u] = v
            que.append(u)
    for i in range(1, n + 1):
        if i == start:
            continue
        if dist[i] == -1:
            continue
        if start in graph[i]:
            if res[0] > dist[i] + 1:
                res = (dist[i] + 1, i)
    if res[0] == infi:
        return -1, []
    cycle_num = res[0]
    v = res[1]
    CYCLE = deque([])
    while v > 0:
        CYCLE.appendleft(v)
        v = par[v]

    return cycle_num, CYCLE


jisho = {}
ans = (-1, [])
cycle_num = infi
kouho_v = -1
for i in range(1, n + 1):
    temp_num, temp_cycle = bfs(i)
    if temp_num == -1:
        continue
    if cycle_num > temp_num:
        cycle_num = min(cycle_num, temp_num)
        kouho_v = i
        jisho[i] = temp_cycle

if kouho_v == -1:
    print(-1)
    exit()
else:
    ans_num = cycle_num
    ans_list = jisho[kouho_v]
    print(cycle_num)
    print(*ans_list, sep="\n")

Solution (Python):
from collections import deque
import sys

input = sys.stdin.buffer.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
infi = 10 ** 10


def bfs(start):
    
    res = (infi, -1)
    dist = [-1] * (n + 1)
    par = [-1] * (n + 1)
    que = deque([])
    que.append(start)
    dist[start] = 0
    while que:
        v = que.popleft()
        for u in graph[v]:
            if dist[u] >= 0:
                continue
            dist[u] = dist[v] + 1
            par[u] = v
            que.append(u)
    for i in range(1, n + 1):
        if i == start:
            continue
        if dist[i] == -1:
            continue
        if start in graph[i]:
            if res[0] > dist[i] + 1:
                res = (dist[i] + 1, i)
    if res[0] == infi:
        return -1, []
    cycle_num = res[0]
    v = res[1]
    CYCLE = deque([])
    while v > 0:
        CYCLE.appendleft(v)
        v = par[v]

    return cycle_num, CYCLE


jisho = {}
ans = (-1, [])
cycle_num = infi
kouho_v = -1
for i in range(1, n + 1):
    temp_num, temp_cycle = bfs(i)
    if temp_num == -1:
        continue
    if cycle_num > temp_num:
        cycle_num = min(cycle_num, temp_num)
        kouho_v = i
        jisho[i] = temp_cycle

if kouho_v == -1:
    print(-1)
    exit()
else:
    ans_num = cycle_num
    ans_list = jisho[kouho_v]
    print(cycle_num)
    print(*ans_list, sep="\n")

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 find_loop(index, visited, cycle):
    visited[index] = True
    cycle.append(index)
    for i in edges[index]:
        if visited.get(i):
            return cycle[cycle.index(i):]
        ret = find_loop(i, visited, cycle)
        if ret:
            return ret
    visited[index] = False
    cycle.pop(-1)
    return None

def find_local_minimum(cycle):
    nxt = {i: j for (i, j) in zip(cycle, cycle[1:] + cycle[:1])}
    processed = set()
    i = cycle[0]
    while i not in processed:
        processed.add(i)
        for j in edges[i]:
            if j in nxt:
                k = nxt[i]
                while k != j:
                    k = nxt.pop(k)
                nxt[i] = j
        i = nxt[i]
    start = i
    ret = [i]
    i = nxt[i]
    while i != start:
        ret.append(i)
        i = nxt[i]
    return ret

cycle = None
visited = {}
for start in range(n):
    if start not in visited:
        cycle = find_loop(start, visited, [])
        if cycle:
            break

if cycle:
    ret = find_local_minimum(cycle)
    print(len(ret))
    for i in ret:
        print(i + 1)
else:
    print(-1)

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 find_loop(index, visited, cycle):
    visited[index] = True
    cycle.append(index)
    for i in edges[index]:
        if visited.get(i):
            return cycle[cycle.index(i):]
        ret = find_loop(i, visited, cycle)
        if ret:
            return ret
    visited[index] = False
    cycle.pop(-1)
    return None

def find_local_minimum(cycle):
    nxt = {i: j for (i, j) in zip(cycle, cycle[1:] + cycle[:1])}
    processed = set()
    i = cycle[0]
    while i not in processed:
        processed.add(i)
        for j in edges[i]:
            if j in nxt:
                k = i
                while k != j:
                    l = nxt[k]
                    del nxt[k]
                    k = l
                nxt[i] = j
        i = nxt[i]
    start = i
    ret = [i]
    i = nxt[i]
    while i != start:
        ret.append(i)
        i = nxt[i]
    return ret

cycle = None
visited = {}
for start in range(n):
    if start not in visited:
        cycle = find_loop(start, visited, [])
        if cycle:
            break

if cycle:
    ret = find_local_minimum(cycle)
    print(len(ret))
    for i in ret:
        print(i + 1)
else:
    print(-1)

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 dfs(index, visited, cycle):
    visited[index] = True
    cycle.append(index)
    for i in edges[index]:
        if visited.get(i):
            return cycle[cycle.index(i):]
        ret = dfs(i, visited, cycle)
        if ret:
            return ret
    visited[index] = False
    cycle.pop(-1)
    return None

def find_local_minimum(cycle):
    n = len(cycle)
    ind = {v: i for (i, v) in zip(range(n), cycle)}
    ret = []
    i = 0
    while True:
        ret.append(i)
        nxt = 0
        for j in [ind[v] for v in edges[cycle[i]] if v in ind]:
            if j < i:
                j += n
            nxt = max(nxt, j)
        if nxt >= n:
            ret = ret[ret.index(nxt % n):]
            break
        i += 1
        while i < nxt:
            del ind[cycle[i]]
            i += 1
    return [cycle[i % n] for i in ret]

cycle = None
visited = {}
for start in range(n):
    if start not in visited:
        cycle = dfs(start, visited, [])
        if cycle:
            break

if cycle:
    ret = find_local_minimum(cycle)
    print(len(ret))
    for i in ret:
        print(i + 1)
else:
    print(-1)

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


n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)

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

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

for u in range(n):
    pos = dfs(u, -1)
    if pos>=0:
        hist = cycle(hist, pos)
        while True:
            us = set(hist)
            update = False
            for i,u in enumerate(hist):
                nu = hist[(i+1)%len(hist)]
                pu = hist[(i-1)]
                if (ns[u]&us)-set([nu, pu]):
                    for v in (ns[u]&us)-set([nu, pu]):
                        break
                    j = hist.index(v)
                    if i<j:
                        hist = hist[i:] + hist[:j+1]
                    else:
                        hist = hist[j:i+1]
                    update = True
                    break
            if not update:
                break
        print(len(hist))
        write("\n".join(map(lambda x: str(x+1), hist)))
        break
else:
    print(-1)

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)

ret = [0] * (n + 1)
for start in range(n):
    parent = [-1] * n
    q = [start]
    while len(q) > 0:
        i = q.pop(0)
        for j in edges[i]:
            if j == start:
                loop = [i]
                while i != start:
                    i = parent[i]
                    loop.append(i)
                if len(ret) > len(loop):
                    ret = loop
                break
            if parent[j] == -1:
                parent[j] = i
                q.append(j)

if len(ret) > n:
    print(-1)
else:
    print(len(ret))
    for i in reversed(ret):
        print(i + 1)

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

from collections import defaultdict, deque
g = defaultdict(list)
for a, b in ab:
    g[a-1].append(b - 1)

ans = None
for start in range(n):
    visited = [0] * n
    visited[start] = 1
    q = deque([start])
    prev = [None] * n

    f = False
    while q:
        cur = q.popleft()

        for target in g[cur]:
            if visited[target] == 0:
                visited[target] = 1
                q.append(target)
                prev[target] = cur

            if target == start:
                f = True
                break

        if f:
            break

    if f:
        loop = [target]
        while cur != None:
            loop.append(cur)
            cur = prev[cur]

        loop = loop[::-1]
        v = set(loop)

        f2 = True
        for i in range(len(loop) - 1):
            a, b = loop[i], loop[i+1]

            for target in g[a]:
                if target in v and target != b:
                    f2 = False
                    break

            if f2 == False:
                break

        if f2:
            ans = loop[:-1]
            break

if ans == None:
    print(-1)
else:
    print(len(ans))
    for _ans in ans:
        print(_ans + 1)

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



@mt
def slv(N, M, AB):
    from collections import defaultdict, deque
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)

    def bfs(s):
        q = deque()
        q.append(s)
        prev = {}
        while q:
            u = q.popleft()
            for v in g[u]:
                if v in prev:
                    continue
                q.append(v)
                prev[v] = u
                if v == s:
                    break

        if s not in prev:
            return None

        cycle = [s]
        v = s
        while True:
            v = prev[v]
            if v == s:
                break
            cycle.append(v)
        return cycle

    ans = None
    for i in range(1, N+1):
        t = bfs(i)
        if t is not None:
            if ans is None:
                ans = t
            else:
                ans = t if len(t) < len(ans) else ans
    if ans is not None:
        return [len(ans)] + ans
    return [-1]


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(*slv(N, M, AB), sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

graph=[set() for _ in range(N+1)]
for _ in range(M):
  A,B=map(int,input().split())
  graph[A].add(B)


visited=[False]*(N+1)
def dfs(path):
  global cycle
  u=path[-1]
  
  visited[u]=True  
  for v in graph[u]:
    if visited[v]:
      cycle=list(path+[v])
      return
    else:
      dfs(path+[v])      
    if cycle:
      return    
  visited[u]=False
  
cycle=[]
for i in range(1,N+1):
  dfs([i])
  if cycle:
    break
else:
  print(-1)
  sys.exit(0)
    

for i in range(len(cycle)):
  if cycle[i]==cycle[-1]:
    cycle=cycle[i:]
    break


cycle_set=set(cycle)
subgraph=[set() for _ in range(N+1)]
for c in cycle_set:
  for v in graph[c]:
    if v in cycle_set:
      subgraph[c].add(v)



ex_path=[]
def dfs2(path,t):
  global ex_path
  u=path[-1]
  if u==t:
    ex_path=path
    return
  
  for v in graph[u]:
    dfs2(path+[v],t)
    if ex_path:
      return

graph=subgraph
while True:
  for i in range(len(cycle)-1):
    u=cycle[i]
    v=cycle[i+1]
    w=-1
    if len(graph[u])>1:
      for x in graph[u]:
        if x!=v:
          w=x
          break
      break
  else:
    print(len(cycle)-1)
    for i in range(len(cycle)-1):
      print(cycle[i])
    sys.exit(0)
    
  
  
  dfs2([w],u)
  cycle=ex_path+[w]
  
  cycle_set=set(cycle)
  subgraph=[set() for _ in range(N+1)]
  for c in cycle_set:
    for v in graph[c]:
      if v in cycle_set:
        subgraph[c].add(v)
        
  graph=subgraph

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

    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)
    def bfs(start):
        pre = [-1]*n
        d = deque([start])

        while d:
            v = d.popleft()
            for nv in adj[v]:
                if nv == start:
                    path = []
                    while v != -1:
                        path.append(v+1)
                        v = pre[v]
                    return path

                if pre[nv] != -1:
                    continue
                pre[nv] = v
                d.append(nv)

        return []
    
    res = [0]*(n+1)
    for i in range(n):
        temp = bfs(i)
        if 0 < len(temp) < len(res):
            res = temp
    if len(res) <= n:
        print(len(res))
        print(*res, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

    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)



    def bfs(start):
        pre = [-1]*n
        d = deque([start])

        while d:
            v = d.popleft()
            for nv in adj[v]:
                if nv == start:
                    path = []
                    while v != -1:
                        path.append(v+1)
                        v = pre[v]
                    return path

                if pre[nv] != -1:
                    continue
                pre[nv] = v
                d.append(nv)

        return -1
    
    res = [0]*(n+1)
    for i in range(n):
        temp = bfs(i)
        if temp != -1 and len(res) > len(temp):
            res = temp
    if len(res) <= n:
        print(len(res))
        print(*res, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

    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)



    def bfs(start):
        pre = [-1]*n
        d = deque([start])
        res = []

        while d:
            v = d.popleft()
            for nv in adj[v]:
                if nv == start:
                    path = []
                    while v != -1:
                        path.append(v+1)
                        v = pre[v]
                        res = path
                    break

                if pre[nv] != -1:
                    continue
                pre[nv] = v
                d.append(nv)

        return res
    
    res = [0]*(n+1)
    for i in range(n):
        temp = bfs(i)
        if temp and len(res) > len(temp):
            res = temp
    if len(res) <= n:
        print(len(res))
        print(*res, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
































def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

    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)


    def bfs(start):
        pre = [-1]*n
        d = deque([start])
        res = []

        while d:
            v = d.popleft()
            for nv in adj[v]:
                if nv == start:
                    path = []
                    while v != -1:
                        path.append(v+1)
                        v = pre[v]
                    if not res or len(res) > len(path):
                        res = path
                    break

                if pre[nv] != -1:
                    continue
                pre[nv] = v
                d.append(nv)

        return res
    
    res = [0]*(n+1)
    for i in range(n):
        temp = bfs(i)
        if temp and len(res) > len(temp):
            res = temp
    if len(res) <= n:
        print(len(res))
        print(*res, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

    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)

    
    def dfs(s, v):
        for nv in adj[v]:
            if nv == s:
                return [v]
            if visited[nv] == 1:
                continue
            visited[nv] = 1
            res = dfs(s, nv)
            if res != -1:
                res.append(v)
                return res
        return -1


    for s in range(n):
        visited = [0]*n
        visited[s] = 1
        heiro = dfs(s, s)
        if heiro != -1:
            break
    else:
        print(-1)
        exit()
    heiro = heiro[::-1]

    def graph(s, g):
        res = [s]
        d = deque([s])
        for i in range(len(heiro)):
            if heiro[i] == s:
                idx = i
                break
        while d:
            v = d.popleft()
            for nv in adj[v]:
                if visited[nv] == 1 and nv == g:
                    res.append(nv)
                    return res
            d.append(heiro[idx+1])
            res.append(heiro[idx+1])
            idx += 1
            if idx == len(heiro)-2:
                idx = -1
            
            if res[-1] == heiro[heiro.index(s)-1]:
                return res

    while True:
        heiro.append(heiro[0])
        visited = [0]*n
        f = 0
        for i in heiro:
            visited[i] = 1
        new_heiro = [heiro[0]]
        for i in range(len(heiro)-1):
            for nv in adj[heiro[i]]:
                if visited[nv] == 1 and nv != heiro[i+1]:
                    new_heiro = graph(nv, heiro[i])
                    f = 1
                    break
            else:
                new_heiro.append(heiro[len(new_heiro)])
            if f:
                heiro = new_heiro
                break
        else:
            break

    print(len(heiro)-1)
    for i in heiro[:-1]:
        print(i+1)

if __name__ == '__main__':
    main()