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 heapq


def dijkstra(adj, start):
    
    prev = [0] * len(adj)
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to in v_tos:
            if min_dist + v_to[1] < dist[v_to[0]]:
                dist[v_to[0]] = min_dist + v_to[1]
                prev[v_to[0]] = v_from
                heapq.heappush(q, [dist[v_to[0]], v_to[0]])
    return dist, prev


N, M = map(int, input().split())
adj = [[] for _ in range(2 * N + 1)]
flg = 1
see = [0] * (N + 1)
for _ in range(M):
    A, B = map(int, input().split())
    adj[A].append([B, 1])
    adj[A].append([B + N, 1])

ans_best = []
len_ans = N+1
for start in range(1, N+1):
    if flg == 0:
        if see[start] == 0:
            continue
    ans = []
    dist, prev = dijkstra(adj, start)
    if dist[start + N] < 10 ** 10:
        k = start + N
        while k != start:
            k = prev[k]
            ans.append(k)
        if len(ans) < len_ans:
            ans_best = ans
            len_ans = len(ans)
            if flg:
                for a in ans:
                    see[a] = 1
                flg = 0

if len_ans == N+1:
    print(-1)
else:
    print(len_ans)
    for a in ans_best:
        print(a)

Solution (Python):
from collections import deque


def main():
    
    
    

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

    AB = [
        [int(a) for a in input().split()]
        for _ in range(M)
    ]

    pp = [[] for _ in range(N)]
    for a, b in AB:
        pp[a - 1].append(b - 1)

    startpool = set(range(N))

    result = None

    while len(startpool) != 0:
        start = min(startpool)

        q = deque([(start, [start])])
        renketu = {start}
        while len(q) != 0:
            p, history = q.popleft()
            target = pp[p]
            for t in target:
                if t in history:
                    if result is None:
                        result = history
                    elif len(result) > len(history) - history.index(t):
                        result = history[history.index(t):]
                if t not in renketu:
                    q.append([t, history + [t]])

                renketu.add(t)
        startpool -= renketu

    if result is not None:
        print(len(result))
        for a in result:
            print(a + 1)
        return
    else:
        print(-1)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
N, M = map(int, input().split())
X = [[] for i in range(N*3)]
for i in range(M):
    x, y = map(int, input().split())
    X[x-1].append(y-1)

INF = 1<<100
def BFS(n, E, i0=0):
    Q = deque([a for a in E[i0]])
    D = [INF] * n
    for a in E[i0]:
        D[a] = 1
    while Q:
        x = Q.popleft()
        for c in X[x]:
            if D[c] == INF:
                D[c] = D[x] + 1
                Q.append(c)
    return D

Y = [BFS(N, X, i)[i] for i in range(N)]

mi = min(Y)
if mi == INF:
    print(-1)
else:
    for i in range(N):
        if Y[i] == mi:
            s = i
            break
    Z = [-1] * N
    for i in range(N):
        for j in X[i]:
            if Y[j] == mi:
                Z[i] = j
                break
    for i in range(N):
        s = Z[s]
    print(mi)
    for i in range(mi):
        s = Z[s]
        print(s+1)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n = I()
    print((n-(n>>1))/n)
    return


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


def C():
    n = I()
    a = LI()
    b = [(a[i],i+1) for i in range(n)]
    b.sort()
    ans = [b[i][1] for i in range(n)]
    print(*ans)
    return


def D():
    def divisor(n):
        if n < 4:
            return set([n])
        res = set([1])
        i = 2
        m = n
        while i**2 <= n:
            if m%i == 0:
                while m%i == 0:
                    m //= i
                res.add(i)
            i += 1
        res.add(m)
        return res
    a,b = LI()
    if min(a,b) == 1:
        print(1)
        return
    s = divisor(a)
    t = divisor(b)
    s &= t
    print(len(s))
    return


def E():
    n,m = LI()
    v = []
    for i in range(m):
        a,b = LI()
        c = LI()
        s = 0
        for j in c:
            s |= 1<<(j-1)
        v.append((a,s))
    l = 1<<n
    dp = [[float("inf")]*l for i in range(m+1)]
    dp[0][0] = 0
    for i in range(m):
        ni = i+1
        a,c = v[i]
        for b in range(l):
            if dp[i][b] == float("inf"):
                continue
            nb = b|c
            nd = dp[i][b]+a
            if nd < dp[ni][nb]:
                dp[ni][nb] = nd
            nd = dp[i][b]
            if nd < dp[ni][b]:
                dp[ni][b] = nd
    if dp[m][-1] == float("inf"):
        print(-1)
    else:
        print(dp[m][-1])
    return


def F():
    def dfs(x,d):
        for y in v[x]:
            if now[y] == True:
                z = x
                d[z] = 2
                while z != y:
                    z = pre[z]
                    d[z] = 2
                k.append(1)

            elif not d[y]:
                d[y] = 1
                pre[y] = x
                now[y] = True
                dfs(y,d)
                now[y] = False

    def dijkstra(s):
        dist = defaultdict(lambda : float("inf"))
        dist[(s,0)] = 0
        q = [(0,s,0)]
        pre = [None]*n
        while q:
            dx,x,k = heappop(q)
            if x == s and k:
                break
            for y in v[x]:
                if d[y] != 2:
                    continue
                if y == s:
                    nk = 1
                else:
                    nk = 0
                nd = dx+1
                if nd < dist[(y,nk)]:
                    dist[(y,nk)] = nd
                    pre[y] = x
                    heappush(q,(nd,y,nk))
        return (dist,pre)

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

    d = [0]*n
    pre = [None]*n
    now = [False]*n
    k = []
    for x in range(n):
        if not d[x]:
            d[x] = 1
            now[x] = True
            dfs(x,d)
            if k:
                break
            now[x] = False
    else:
        print(-1)
        return
    di,p,s = float("inf"),[],None
    for x in range(n):
        if d[x] != 2:
            continue
        dist,pre = dijkstra(x)
        if dist[(x,1)] < di:
            di = dist[(x,1)]
            p = pre
            s = x
    ans = [s+1]
    x = p[s]
    while x != s:
        ans.append(x+1)
        x = p[x]
    ans.sort()
    print(len(ans))
    for i in ans:
        print(i)
    return


if __name__ == "__main__":
    F()

Solution (Python):
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components
import numpy as np
from collections import defaultdict

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

if M == 0:
    print(-1)
    exit()

AB = [tuple(int(x) for x in line.split()) for line in readlines()]

A,B = zip(*AB)
graph = csr_matrix(([1]*M,(A,B)),(N+1,N+1))
_,comp = connected_components(graph,connection='strong')

size = np.bincount(comp)

if size.max() == 1:
    print(-1)
    exit()

n = np.where(size > 1)[0][0]

V = set(np.where(comp == n)[0])

graph = [[] for _ in range(N+1)]
for a,b in AB:
    if a in V and b in V:
        graph[a].append(b)


order = defaultdict(int)
x = V.pop()
V.add(x)
q = [x]
order[x] = 1
path = [x]
flag = False
while True:
    y = graph[x][0]
    if order[y] != 0:
        path = path[order[y]-1:]
        break
    path.append(y)
    order[y] = order[x] + 1
    x = y

V = set(path)
next_v = {u:v for u,v in zip(path,path[1:])}; next_v[path[-1]] = path[0]


for a,b in AB:
    if not (a in V and b in V):
        continue
    
    x = next_v[a]
    while x != b:
        V.remove(x)
        x = next_v[x]
    next_v[a] = b

print(len(V))
print(*V,sep='\n')

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, m = na()
g = [[False] * n for _ in range(n)]
gs = [[] for _ in range(n)]
for i in range(m):
    s, t = na()
    gs[s-1].append(t-1)
    g[s-1][t-1] = True

ans = 999999
best = None
for i in range(n):
    ds = [9999999] * n
    prevs = [-1] * n
    ds[i] = 0
    q = [i]
    qp = 0
    while qp < len(q):
        cur = q[qp]
        qp += 1
        for e in gs[cur]:
            if ds[e] > ds[cur] + 1:
                ds[e] = ds[cur] + 1
                prevs[e] = cur
                q.append(e)
    for j in range(n):
        if g[j][i]:
            if ds[j] + 1 < ans:
                ans = ds[j] + 1
                best = [0] * (ds[j]+1)
                best[0] = i
                cur = j
                r = -1
                while cur != i:
                    best[r] = cur
                    r -= 1
                    cur = prevs[cur]

if not best:
    print(-1)
else:
    print(ans)
    for x in best:
        print(x+1)