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):
INF = float('inf')
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, From, To, cost=1):
        self.graph[From].append((To,cost))

    def get_nodes(self):
        return self.graph.keys()

class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda:INF)
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q,(self.dist[start], start))

        while  self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, cost in self.g[u]:
                alt = dist_u + cost
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q,(alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]

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

for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g.add_edge(a,b)

ans = INF
d = [Dijkstra(g,i).dist for i in range(N)]
k = -1
l = -1
for i in range(N-1):
    for j in range(i+1,N):
        if d[i][j]+d[j][i] < ans:
            k = i
            l = j
            ans = d[i][j]+d[j][i]
    
if ans != INF:
    path = Dijkstra(g,k).shortest_path(l)[:-1]+Dijkstra(g,l).shortest_path(k)[:-1]
    print(ans)
    for node in path:
        print(node+1)
else:
    print(-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 dijkstra(s):
        dist = defaultdict(lambda : float("inf"))
        dist[(s,0)] = 0
        q = deque([(s,0)])
        pre = [None]*n
        while q:
            x,k = q.popleft()
            dx = dist[(x,k)]
            if x == s and k:
                break
            nd = dx+1
            for y in v[x]:
                if y == s:
                    nk = 1
                else:
                    nk = 0
                if dist[(y,nk)] == float("inf"):
                    dist[(y,nk)] = nd
                    pre[y] = x
                    q.append((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)

    di,p,s = float("inf"),[],None
    for x in range(n):
        dist,pre = dijkstra(x)
        if dist[(x,1)] < di:
            di = dist[(x,1)]
            p = pre
            s = x
    if di == float("inf"):
        print(-1)
        return
    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):

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

    di,p,s = float("inf"),[],None
    for x in range(n):
        dist,pre = dijkstra(x)
        if dist[(x,1)] < di:
            di = dist[(x,1)]
            p = pre
            s = x
    if di == float("inf"):
        print(-1)
        return
    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
sys.setrecursionlimit(500000)
def scc(N, G, RG):
    
    order = []
    used = [0]*N
    group = [None]*N
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
    def rdfs(s, col):
        group[s] = col
        used[s] = 1
        for t in RG[s]:
            if not used[t]:
                rdfs(t, col)
    for i in range(N):
        if not used[i]:
            dfs(i)
    used = [0]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs(s, label)
            label += 1
    return label, group

from collections import Counter
N, M = map(int, input().split())
E = [[] for _ in range(N+1)]
E_set = [set() for _ in range(N+1)]
E_rev = [[] for _ in range(N+1)]
E_rev_set = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E_set[a].add(b)
    E_rev[b].append(a)
    E_rev_set[b].add(a)

label, group = scc(N+1, E, E_rev)
cnt = Counter(group)
Closed = [False] * (N+1)

grooo = [set() for _ in range(N+1)]
for v, gr in enumerate(group):
    grooo[gr].add(v)

from random import random
haaaaaaaaaaaaaaaaaaaaaaa = enumerate(group) if random() > 0.5 else zip(range(N, 0, -1), group[::-1])


for v, gr in haaaaaaaaaaaaaaaaaaaaaaa:
    if Closed[gr]:
        continue
    Closed[gr] = True
    if cnt[gr]==1:
        continue

    
    groo = grooo[gr]

    path = [v]
    path_set = {v}
    while True:
        
        aaa = E_set[v]&path_set
        if aaa:
            break
        u = (groo&E_set[v]).pop()
        
        while E_rev_set[u]-{v} & path_set:
            path_set.remove(path.pop())
        path.append(u)
        path_set.add(u)
        v = u
        
    for i, v in enumerate(path):
        if v in aaa:
            aaa.remove(v)
            if len(aaa)==0:
                break
    ans = path[i:]
    print(len(ans))
    print("\n".join(map(str, ans)))
    exit()
print(-1)

Solution (Python):
INF = float('inf')
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, From, To, cost=1):
        self.graph[From].append((To,cost))

    def get_nodes(self):
        return self.graph.keys()

class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda:INF)
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q,(self.dist[start], start))

        while  self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, cost in self.g[u]:
                alt = dist_u + cost
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q,(alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]

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

for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g.add_edge(a,b)
    g.add_edge(a,b+N)
    g.add_edge(a+N,b)

ans = INF
j = -1

for i in range(N):
    d = Dijkstra(g,i).dist
    if d[i+N] < ans:
        ans = int(d[i+N])
        j = i

if ans != INF:
    path = Dijkstra(g,j).shortest_path(j+N)[:-1]
    print(ans)
    for node in path:
        print(node+1)
else:
    print(-1)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 


from collections import deque
def bfs(g,root,memo,backtrack):
    q = deque()

    memo[root] = 0
    q.append(root)
    """BFS"""
    while q: 
        v = q.popleft() 
        for c in g[v]:
            if memo[c] > 0: continue 
            
            memo[c] = memo[v] + 1
            backtrack[c] = v
            q.append(c)



n,m = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]

for _ in range(m):
    a,b = [int(i)-1 for i in readline().split()]
    g[a].append(b)

res = 1000000
v0 = -1
b0 = None

for v in range(n):
    memo = [-1]*n
    backtrack = [-1]*n
    bfs(g,v,memo,backtrack)
    if 1 < memo[v] < res:
        v0 = v
        b0 = backtrack
        res = memo[v]



if res == 1000000: print(-1)
else:
    i = b0[v0]
    ans = [i+1]
    while i != v0:
        i = b0[i]
        ans.append(i+1)
    ans.reverse()
    
    print(res)
    print(*ans,sep="\n")

Solution (Python):

N, M = [int(x) for x in input().strip().split(" ")]

def dfs(v, l):
    for u in d[v]:
        if u in pvs:
            return l + [u]
        if u in vs:
            continue
        pvs.add(u)
        vs.add(u)
        ll = dfs(u, l + [u])
        pvs.remove(u)
        if ll:
            return ll
    return False

d = [set() for _ in range(N)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a-1].add(b-1)

vs = set()
for i in range(N):
    if i in vs:
        continue
    vs.add(i)
    pvs = set([i])
    loop = dfs(i, [i])

    if loop:
        break

import sys

if not loop:
    print("-1")
    sys.exit()
else:
    ll = []
    lx = loop[-1]
    f = False
    for x in loop:
        if lx == x and not f:
            f = True
            continue
        if not f:
            continue
        ll.append(x)
    loop = ll

v2i = [-1 for _ in range(N)]
for i, v in enumerate(loop):
    v2i[v] = i

i = 0
vs = set()
ss = set()
lnum = len(loop)
ll = []
while True:
    v = loop[i]
    if i in vs:
        f = False
        loop = []
        for x in ll:
            if v == x:
                f = True
            if f:
                loop.append(x)
        break

    m = 0

    for u in d[v]:
        if v2i[u] == -1:
            continue
        if v2i[u] in ss:
            continue
        if v2i[v] > v2i[u]:
            m = max(lnum - v2i[v] + v2i[u], m)
        else:
            m = max(v2i[u] - v2i[v], m)

    for j in range(m-1):
        ss.add((i + j + 1) % lnum)
    vs.add(i)
    ll.append(v)

    i = (i + m) % lnum


print(len(loop))
for i in loop:
    print(i+1)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import dijkstra

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]
N, M = map(int,input().split())
g = [[np.inf]*(2*N) for _ in range(2*N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a][b] = 1
    g[a][b+N] = 1
    g[a+N][b] = 1

ans = np.inf
j = -1
d = dijkstra(g,return_predecessors=True)

for i in range(N):
    if d[0][i][i+N] < ans:
        ans = int(d[0][i][i+N])
        j = i

if ans != np.inf:
    path = get_path(j,j+N,d[1])[::-1][:-1]
    path = [node%N for node in path]
    print(ans)
    for node in path:
        print(node+1)
else:
    print(-1)

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

e_list = [[] for i in range(N)]
es = []
for i in range(M):
    a,b = list(map(int,input().split()))
    a,b = a-1,b-1
    es.append((a,b))
    e_list[a].append(b)

from collections import deque
flag=False
min_d = 10**27
for vg,vi in es:
    Q = deque([vi])
    checked_list = [False for i in range(N)]
    checked_list[vi]=True
    min_path_list = [10**27 for i in range(N)] 
    min_path_list[vi] = 0
    prev_list = [-1]*N
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if v!=vg or v1!=vi:
                if not checked_list[v1]:
                    checked_list[v1]=True
                    Q.appendleft(v1)
                    prev_list[v1]=v
                    min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) 
    if min_path_list[vg]<min_d:
        flag=True
        min_vi = vi
        min_vg = vg
        min_d = min_path_list[vg]
        min_prev = prev_list
            

if flag:
    ans = []
    v = min_vg
    while v!=min_vi:
        ans.append(v+1)
        v=min_prev[v]
    ans.append(min_vi+1)
    ans = ans[::-1]
    
    print(len(ans))
    for a in ans:
        print(a)
else:
    print(-1)

Solution (Python):
def search(N, M, adj):
    reachable = [[set() for i in range(N)] for _ in range(N)]
    reachable[0] = adj
    start = -1
    for m in range(1, N):
        prev = reachable[m-1]
        cur = reachable[m]
        
        
        for i in range(N):
            for nxt in adj[i]:
                for p in prev[nxt]:
                    cur[i].add(p)
                if i in prev[nxt]:
                    return (i, reachable, m+1)
    return None


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        adj[A-1].add(B-1)
    result = search(N, M, adj)
    if not result:
        print(-1)
        return
    start, reachable, cnt = result
    ans = [-1] * cnt
    x = start
    for i in range(cnt):
        ans[i] = x+1
        for nxt in adj[x]:
            if start in reachable[cnt-i-2][nxt]:
                x = nxt
                break
    print(len(ans))
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Solution (Python):
from random import shuffle

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

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


def cycle(E, visited):
    path_set = [False]*N
    path = []
    def dfs(v):
        if path_set[v]:
            path.append(v)
            return True
        if visited[v]:
            return False
        visited[v] = True
        path.append(v)
        path_set[v] = True
        for u in E[v]:
            if dfs(u):
                return True
        path.pop()
        path_set[v] = False
        return False

    while True:
        try:
            v = visited.index(False)
            if dfs(v):
                return path[path.index(path[-1]):-1]
        except ValueError:
            return None

c = cycle(E, [False]*N)
if c is None:
    print(-1)
    exit()

while True:
    c_set = set(c)
    cnt = 0
    for u in c:
        E[u] = [v for v in E[u] if v in c_set]
        shuffle(E[u])
        cnt += len(E[u])
    if cnt == len(c):
        break
    else:
        visited = [True]*N
        for v in c:
            visited[v] = False
        c = cycle(E,visited)

print(len(c))
for u in c:
    print(u+1)

Solution (Python):
from collections import deque


def solve_f(n, g):

    for i in range(n):
        parent = [-1] * n
        queue = deque([i])
        done = False
        answer = []
        
        while len(queue) > 0:
            p = queue.popleft()
            for q in g[p]:
                if q == i:
                    r_list = []
                    r = p
                    while r != -1:
                        r_list.append(r)
                        r = parent[r]
                    
                    check = 1
                    for r in r_list:
                        check = max(len(set(g[r]).intersection(r_list)), check)
                    if check == 1:
                        return [len(r_list)] + [r + 1 for r in r_list]
                elif parent[q] == -1:
                    parent[q] = p
                    queue.append(q)

    return [-1]


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        g[a - 1].append(b - 1)
    res = solve_f(n, g)
    for r in res:
        print(r)


if __name__ == "__main__":
    main()

Solution (Python):
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
Eb = [{} for _ in [0]*N]
for a,b in AB:
    E[a-1][b-1] = 1
    Eb[b-1][a-1] = 1

import heapq
def Dijkstra(N,E,start):
    d = [-1]*N
    q = [(0,start)]
    while q:
        ci,i = heapq.heappop(q)
        if d[i]!= -1:continue
        d[i] = ci
        for j,cj in E[i].items():
            if d[j]!=-1:continue
            heapq.heappush(q,(ci+cj,j))
    return d
INF = N*10
ans = [INF]
for i in range(N):
    d = Dijkstra(N,E,i)
    j = -1
    dj = INF
    for k in Eb[i]:
        if d[k]>0 and d[k]<dj:
            j = k
            dj = d[k]
    if (j!=-1) and ((dj+1) < ans[0]):
        ans = [dj+1,i+1]
        while j!=i:
            ans.append(j+1)
            dj = d[j]
            for k in Eb[j]:
                if d[k] == dj-1:
                    j = k
                    dj = d[k]
                    break

if ans[0] == INF : ans = [-1]
for out in ans:
    print(out)

Solution (Python):
N, M = map(int, input().split())
neighbours = [[] for i in range(N)]
for i in range(M):
    A, B = map(lambda x:int(x)-1,input().split())
    neighbours[A].append(B)

visited = [False for i in range(N)]
def bfs(node):
    parents = [None for i in range(N)]
    stack = [node]
    while stack:
        item = stack.pop(0)
        orig = item
        for neighbour in neighbours[item]:
            if visited[neighbour]:
                if parents[neighbour] == None:
                    parents[neighbour] = item
                try:
                    graph = {neighbour}
                    while item != neighbour:
                        graph.add(item)
                        item = parents[item]
                        if item == orig and item != neighbour:
                            1/0
                    print(len(graph))
                    for item in graph:
                        print(item+1)
                    return True
                except:
                    pass
            if not visited[neighbour]:
                parents[neighbour] = item
                visited[neighbour] = True
                stack.append(neighbour)
            
for i in range(N):
    if not visited[i]:
        if bfs(i):
            break
else:
   print(-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 dx < dist[(x,k)]:
                continue
            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):
from collections import deque
import sys

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

AB = []
lis = [ [] for i in range(N)]

for i in range(M):

    A,B = map(int,input().split())

    A -= 1
    B -= 1

    lis[A].append(B)

q = deque([])

first = [-1] * (N+1)
first[0] = 0
first[-1] = 0

q.append( first )

end = [True] * N
end[0] = False

while len(q) > 0:

    now = q.pop()
    lasp = now[-1]
    nownum = now[lasp] 

    

    for nex in lis[lasp]:

        if now[nex] == -1:
            ncopy = now.copy()
            ncopy[nex] = nownum + 1
            ncopy[-1] = nex
            end[nex] = False
            q.append(ncopy)

        else:

            flag = True

            for i in range(N):

                if now[i] >= 0:

                    for j in lis[i]:

                        if (now[j] >= now[nex] and now[j] != now[i] + 1) and not (i == lasp and j == nex):
                            flag = False
                            break

                if not flag:
                    break

            if flag:
                ans = []

                for i in range(N):
                    if now[i] >= now[nex]:
                        ans.append(i + 1)

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

                sys.exit()

    if len(q) == 0:
        for i in range(N):
            if end[i]:

                first = [-1] * (N+1)
                first[i] = 0
                first[-1] = i
                q.append(first)
                end[i] = False
                break
            

print (-1)