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-----
4 5
1 2
2 3
2 4
4 1
4 3

-----Sample Output-----
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.

Difficulty: interview

Starter code:

Solutions:
from collections import deque

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

INF = 10**18

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

g = Graph(N, edge)

loopsize = INF

for i in range(N):
    root = i
    queue = deque([root])
    dist = [INF for _ in range(N)]
    dist[root] = 0
    prev = [None for _ in range(N)]
    while queue:
        node = queue.popleft()
        for adj in g.graph[node]:
            if adj == root: #閉路を検出する
                dist[root] = dist[node] + 1
                prev[root] = node
                break
            if dist[adj] != INF:
                continue
            dist[adj] = dist[node] + 1
            prev[adj] = node
            queue.append(adj)
        else:
            continue
        break
    else:
        continue
    #最小の閉路なら条件を満たす
    if loopsize > dist[root]:
        loopsize = dist[root]
        path = [root]
        node = root
        while prev[node] != root:
            node = prev[node]
            path.append(node)

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

import sys
sys.setrecursionlimit(10**9)

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

def getCycle(adjL):
    def dfs(vNow):
        if isAvails[vNow]:
            anss.append(vNow)
            return vNow
        useds[vNow] = True
        isAvails[vNow] = True
        for v2 in adjL[vNow]:
            vRet = dfs(v2)
            if vRet == vNow or vRet == numV:
                return numV
            elif vRet != -1:
                anss.append(vNow)
                return vRet
        isAvails[vNow] = False
        return -1

    numV = len(adjL)
    useds = [False] * numV
    anss = []
    for vSt in range(numV):
        isAvails = [False] * numV
        if useds[vSt]: continue
        vRet = dfs(vSt)
        if vRet == numV:
            return anss[::-1]
    return []

cycle = getCycle(adjL)

if not cycle:
    print((-1))
    return

isAvails = [False] * N
v2s = [-1] * N
for i in range(len(cycle)):
    isAvails[cycle[i]] = True
    v2s[cycle[i-1]] = cycle[i]

while True:
    adjL2 = [set() for _ in range(N)]
    a, b = -1, -1
    for v in cycle:
        for v2 in adjL[v]:
            if isAvails[v2]:
                adjL2[v].add(v2)
                if v2s[v] != v2:
                    a, b = v, v2

    if (a, b) == (-1, -1):
        print((len(cycle)))
        print(('\n'.join([str(x+1) for x in cycle])))
        break

    adjL = adjL2

    cycle = []
    isAvails = [False] * N
    v2s[a] = b
    v = a
    while not isAvails[v]:
        cycle.append(v)
        isAvails[v] = True
        v = v2s[v]


# find a cycle
def find_cycle(g):
    n = len(g)
    used = [0]*n #0:not yet 1: visiting 2: visited
    for v in range(n): #各点でDFS
        if used[v] == 2: continue
        #初期化
        stack = [v]
        hist =[] #履歴
        while stack:
            v = stack[-1]
            if used[v] == 1:
                used[v] = 2 #帰りがけの状態に
                stack.pop()
                hist.pop()
                continue
            hist.append(v)
            used[v] = 1 #行きがけの状態に
            for c in g[v]:
                if used[c] == 2: continue
                elif used[c] == 1: # cを始点とするサイクル発見！
                    return hist[hist.index(c):]
                else:
                    stack.append(c)
    return None

def find_minimal_cycle(g,cycle):
    n = len(g)
    is_in_cycle = [0]*n #サイクルに使われているか
    nxt = [-1]*n #次の頂点
    
    l = len(cycle)
    for i,c in enumerate(cycle):
        is_in_cycle[c] = 1
        nxt[c] = cycle[i+1-l]

    # 極小サイクルを求める
    for v in cycle:
        if is_in_cycle[v]:
            for c in g[v]:
                if is_in_cycle[c] == 1: #もしショートカット v -> c があれば
                    v0 = nxt[v] #以下サイクルのうち v から c までを削除
                    while v0 != c: 
                        is_in_cycle[v0] = 0 
                        v0 = nxt[v0] 
                    nxt[v] = c # nxt を繋ぎ直す
    
    #極小サイクルの出力
    i = is_in_cycle.index(1)
    v = nxt[i]
    hist = [i] #履歴
    while v != i:
        hist.append(v)
        v = nxt[v]
    return hist
    
    

#########################################################

##########################################################
# coding: utf-8
# Your code here!

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

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)

cycle = find_cycle(g)

if cycle == None: print((-1))
else:
    res = find_minimal_cycle(g,cycle)
    print((len(res)))
    for i in res:
        print((i+1))








def main():
  from collections import deque
  n,m,*t=list(map(int,open(0).read().split()))
  i=[0]*n
  o=[[]for _ in range(n)]
  for a,b in zip(*[iter(t)]*2):
    o[a-1]+=b-1,
    i[b-1]+=1
  q=deque(v for v,f in enumerate(i)if f<1)
  r=[]
  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)))
main()


from collections import*
n,m,*t=map(int,open(0).read().split())
i,o=[0]*n,[[]for _ in range(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)
r=[]
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))

from collections import deque
import sys
sys.setrecursionlimit(10**6)

class DirectedGraph:
    def __init__(self, adj):
        self.n = len(adj)
        self.adj = adj
        self.is_asyclic = False
        self.max_path_len = None

    def topological_sort(self):
        indegree = [0] * self.n
        for i, vs in enumerate(self.adj):
            for dest in vs:
                indegree[dest] += 1
        zero_v = []
        for v, indeg in enumerate(indegree):
            if indeg == 0:
                zero_v.append(v)
        max_path_len = 1
        tp_sorted = []
        to_be_added = []
        while True:
            while zero_v:
                v = zero_v.pop()
                tp_sorted.append(v)
                for dest in self.adj[v]:
                    indegree[dest] -= 1
                    if indegree[dest] == 0:
                        to_be_added.append(dest)
            if len(to_be_added) > 0:
                zero_v += to_be_added
                to_be_added = []
                max_path_len += 1
            else:
                break
        if len(tp_sorted) == self.n:
            self.is_asyclic = True
            self.max_path_len = max_path_len
            return tp_sorted
        else:
            self.is_asyclic = False
            return None

    def extract_cycle(self):
        self.seen = [0] * self.n
        self.checked = [0] * self.n
        self.hist = deque()
        self.node_in_cycle = -1

        def dfs(v):
            self.seen[v] = 1
            self.hist.append(v)
            for nv in self.adj[v]:
                if self.checked[nv]:
                    continue
                if self.seen[nv] and not self.checked[nv]:
                    self.node_in_cycle = nv
                    return
                dfs(nv)
                if self.node_in_cycle != -1:
                    return
            self.hist.pop()
            self.checked[v] = 1

        for i in range(self.n):
            if not self.checked[i]:
                dfs(i)
            if self.node_in_cycle != -1:
                break
        if self.node_in_cycle == -1:
            return []
        else:
            cycle = []
            while self.hist:
                t = self.hist.pop()
                cycle.append(t)
                if t == self.node_in_cycle:
                    break
            cycle.reverse()
            return cycle

n, m = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)

DG = DirectedGraph(edge)
cycle = DG.extract_cycle()

if len(cycle) == 0:
    print(-1)
    return

while True:
    in_cycle = set(cycle)
    deg = [0] * n 
    for item in cycle:
        for v in edge[item]:
            if v in in_cycle:
                deg[v] += 1
    
    ok = True
    for i, item in enumerate(cycle):
        if deg[item] > 1:
            ok = False
            cur_id = start = i
    if ok:
        print(len(cycle))
        print("\n".join([str(item + 1) for item in cycle]))
        return

    ncycle = []
    cur = cycle[cur_id]
    while True:
        ncycle.append(cur)
        if cycle[start] in edge[cur]:
            break
        cur_id = (cur_id + 1) % len(cycle)
        cur = cycle[cur_id]
    cycle = ncycle[:]

from collections import deque

n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
INF = 10 ** 5

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)

mn = INF
for s in range(n):
    dq = deque([s])
    d = [-1] * n
    p = [-1] * n
    d[s] = 0
    last = []

    while dq:
        u = dq.popleft()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                p[v] = u
                dq.append(v)

            if v == s:
                last.append(u)

    for v in last:
        route = [v]
        while p[v] != s:
            v = p[v]
            route.append(v)

        route.append(s)
        size = len(route)
        if size < mn:
            mn = size
            ans = route[::-1]

if mn != INF:
    print(mn)
    for e in ans:
        print((e + 1))
else:
    print((-1))


import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N + 1)]

for a, b in AB:
    graph[a].append(b)


def cycle_size(from_v):
    """
    from_v に戻ってくるまでのステップ数
    :param from_v:
    :return:
    """
    parents = [None] * len(graph)
    seen = [False] * len(graph)
    que = deque([(from_v, 0)])
    while que:
        v, d = que.pop()
        for u in graph[v]:
            if seen[u]:
                continue
            seen[u] = True
            que.appendleft((u, d + 1))
            parents[u] = v
            if u == from_v:
                return d + 1, parents
    return INF, parents


min_v = None
min_size = INF
min_parents = None
for v in range(1, N + 1):
    size, parents = cycle_size(v)
    if size < min_size:
        min_v = v
        min_size = size
        min_parents = parents

if min_size < INF:
    print(min_size)
    print(min_v)
    v = min_parents[min_v]
    while v != min_v:
        print(v)
        v = min_parents[v]
else:
    print((-1))


import sys
sys.setrecursionlimit(500000)
def scc(N, G, RG):
    # https://tjkendev.github.io/procon-library/python/graph/scc.html
    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 = list(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 = list(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 list(zip(list(range(N, 0, -1)), group[::-1]))


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

    #print(gr, cnt[gr])
    groo = grooo[gr]

    path = [v]
    path_set = {v}
    while True:
        #print("v=",v)
        aaa = E_set[v]&path_set
        if aaa:
            break
        u = (groo&E_set[v]).pop()
        #print("u=",u)
        while E_rev_set[u]-{v} & path_set:
            path_set.remove(path.pop())
        path.append(u)
        path_set.add(u)
        v = u
        #print(path)
    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))))
    return
print((-1))


def main():
  from collections import deque
  n,m,*t=map(int,open(0).read().split())
  i,o=[0]*n,[[]for _ in range(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)
  r=[]
  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))
main()

from heapq import heappop, heappush

n, m = map(int, input().split())
xy = [tuple(int(x)-1 for x in input().split()) for _ in range(m)]

R = [[] for _ in range(n)]
h = [0] * n

for x, y in xy:
    R[x].append(y)
    h[y] += 1

S = []

st = []

for i in range(n):
    if h[i] == 0:
        heappush(st, i)

while len(st) > 0:
    temp = heappop(st)
    S.append(temp)
    for x in R[temp]:
        h[x] -= 1
        if h[x] == 0:
            heappush(st, x)

if len(S) != n:
    print(-99999)
else:
    print(-1)

from collections import deque


def main():
    # N = int(input())
    # N,= [int(a) for a in input().split()]
    # N, M = [int(a) for a in input().split()]

    # a = []
    # # b = []
    # c = []
    #
    # for _ in range(M):
    #     aa, bb = [int(a) for a in input().split()]
    #     cc = [int(a) for a in input().split()]
    #     a.append(aa)
    #     # b.append(bb)
    #     c.append(cc)
    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))


def __starting_point():
    main()

__starting_point()

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

#!/usr/bin/env python

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

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

    Ans = [1]*(N+1)
    
    # 全ての頂点から, 閉路が存在しないかを確認する
    for s in range(N):
        prev = [-1]*N
        dist = [-1]*N
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for nv in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    prev[nv] = v
                    dq.append(nv)
                # 次が 0番目(開始地点) なら閉路あり
                if dist[nv] == 0 and prev[nv] == -1:
                    prev[nv] = v

        # 開始地点の前 が -1でない => 閉路あり
        if prev[s] != -1:
            v = prev[s]
            ans = set()
            for _ in range(max(dist)+1):
                ans.add(prev[v])
                v = prev[v]
            if len(Ans) > len(ans):
                Ans = list(ans)
    
    if len(Ans) == N+1:
        print(-1)
    else:
        print(len(Ans))
        Ans.sort()
        for v in Ans:
            print(v+1)

def __starting_point():
    main()
__starting_point()

from collections import deque
n, m = list(map(int, input().split()))
g = [[] for _ in range(n)]
INF = float('inf')
for _ in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    g[a].append(b)

res = []
shortest = n + 1
for s in range(n):
    dist = [-1] * n
    prev = [-1] * n
    q = deque()
    q.append(s)
    dist[s] = 0
    while len(q) != 0:
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                prev[nv] = v
                q.append(nv)
    for t in range(n):
        if t == s:
            continue
        if dist[t] == -1:
            continue
        for nt in g[t]:
            if nt == s:
                temp = [s]
                cur = t
                while cur != s:
                    temp.append(cur)
                    cur = prev[cur]
                if shortest > len(temp):
                    shortest = len(temp)
                    res = temp
if shortest == n + 1:
    print((-1))
    return
print((len(res)))
for v in res:
    print((v + 1))

# def bfs(sv):
#     dist = [INF] * n
#     pre = [-1] * n
#     q = deque()
#     q.append(sv)
#     dist[sv] = 0
#     while q:
#         v = q.popleft()
#         for nv in g[v]:
#             if dist[nv] == INF:
#                 continue
#             pre[nv] = v
#             dist[nv] = dist[v] + 1
#             q.append(nv)
#     print(dist)
#     best = (INF, -1)
#     for v in range(n):
#         if v == sv:
#             continue
#         for nv in g[v]:
#             if nv == sv:
#                 best = min(best, (dist[nv], nv))
#                 print(sv, best)
#                 # print(best)
#     if best[0] == INF:
#         return [0] * (n + 1)
#     print(pre)
#     v = best[1]
#     print('v', v)
#     res = []
#     while v != -1:
#         res.append(v)
#         v = pre[v]
#     print('res', res)
#     return res


# ans = [0] * (n + 1)
# for s in range(n):
#     now = bfs(s)
#     if len(now) < len(ans):
#         print('aa')
#         ans = now
#         print(ans)
# if len(ans) == n + 1:
#     print(-1)
#     return
# print(len(ans))
# for v in ans:
#     print(v)


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)

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:
      # print("stack:", stack)
      curr, visited = stack.pop()
      if curr in visited:
        # print("cycle found:", curr)
        return visited
      else:
        # print("adding in visited:", curr)
        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)

# print("AB:")
# for i in AB:
#   print(i)
cycle = dfs_2(N, AB)
# print("cycle:", cycle)
if not cycle:
    print(-1)
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print(len(cycle))
    for v in cycle:
        print(v + 1)


from collections import deque
def resolve():
    N, M = list(map(int, input().split()))
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = [int(x) - 1 for x in input().split()]
        G[a].append(b)

    shortest = N + 1
    res = []
    for s in range(N):
        dist = [-1] * N
        pre = [-1] * N
        q = deque()
        q.append(s)
        dist[s] = 0
        while q:
            v = q.popleft()
            for to in G[v]:
                if dist[to] == -1:
                    dist[to] = dist[v] + 1
                    pre[to] = v
                    q.append(to)

        for t in range(N):
            if t == s or dist[t] == -1:
                continue
            for to in G[t]:
                if to == s:  # サイクルになっている頂点
                    tmp = [s]
                    cur = t
                    while cur != s:
                        tmp.append(cur)
                        cur = pre[cur]
                    if shortest > len(tmp):
                        shortest = len(tmp)
                        res = tmp

    if shortest == N + 1:
        print((-1))
    else:
        print((len(res)))
        res.sort()
        for v in res:
            print((v + 1))


def __starting_point():
    resolve()

__starting_point()

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

from collections import deque
tmpdist = N
ans = None
for to in range(N):
    for fr in es[to]:
        dist = [N] * N
        dist[fr] = 0
        prev = [-1] * N
        q = deque([fr])
        while q:
            v = q.popleft()
            if v==to: break
            for w in es[v]:
                if dist[w] < N: continue
                if v==to and w==fr: continue
                dist[w] = dist[v] + 1
                prev[w] = v
                q.append(w)
        else:
            continue
        if dist[to] < tmpdist:
            tmpdist = dist[to]
            ans = set()
            v = to
            while 1:
                ans.add(v+1)
                if prev[v] < 0: break
                v = prev[v]
if ans is None:
    print(-1)
else:
    print(len(ans))
    print(*ans, sep='\n')

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 # sからループを探して見つかった時の、ループの最後の頂点番号
    dq.append(s)
    # BFSでループを見つける
    while dq and ans_last is None:
        v = dq.popleft()
        d = dist[v]
        for n in G[v]:
            # 頂点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))
    
    # 見つからなかった場合はNoneを返す
    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)

    # すべての頂点の入次数が 1、出次数が 1 であるような G の誘導部分グラフ
    # [すべての頂点の入次数が 1、出次数が 1 のグラフ] -> ループ

    # 有向グラフ G=(V,E) に対し、次のような条件を満たす有向グラフ G′=(V′,E′) を G の誘導部分グラフと呼ぶ。
    # V′ は V の (空でない) 部分集合である。
    # E′ は、E の辺であって両端点がともに V′ に含まれるものすべてを含む集合である。

    # -> ループでも、ショートカットできるようなループはだめ

    # 例: 1 -> 2 -> 3 -> 4 -> 5
    #     ^    |         ^    |
    #     |    ----------|    |
    #     ---------------------
    # V' = {1, 2, 3, 4, 5} としてしまうと、
    # E' = {(1->2), (2->3), (3->4), (2->4), (4->5), (5->1)}
    # となってしまい、この誘導部分グラフG'=(V', E')において、
    # 頂点2の出次数が2になってしまう。（頂点4の入次数も2になってしまう）
    # V' = {1, 2, 4, 5} とすれば、
    # E' = {(1->2), (2->4), (4->5), (5->1)}
    # となり、すべての頂点の入次数が 1、出次数が 1 となる
    
    # つまり、ショートカットできない最短のループを1つでも見つければよい
    
    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)

def __starting_point():
    main()
__starting_point()

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: # ENTER, EMPTY
            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)
    return

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)

import sys
sys.setrecursionlimit(10**7)
def main():
    N, M = list(map(int, input().split()))
    l = [[] for _ in range(N)]
    for _ in range(M):
        a, b = list(map(int, input().split()))
        l[a-1].append(b-1)
    c = [0] * N
    loop = []
    def cyclic(n):
        if c[n] == 2:
            return False
        if c[n] == 1:
            loop.append(n)
            return True
        c[n] = 1
        for i in l[n]:
            if cyclic(i):
                loop.append(n)
                return True
        c[n] = 2
        return False
    for i in range(N):
        if cyclic(i):
            break
    if len(loop) == 0:
        print((-1))
        return
    print((0))
    return
main()


import sys
from collections import deque


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

    # 答えが見つかるまで、スタート地点は全て試します
    for start in range(1, N+1):
        visited = [0]*(N+1)

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

        while dq:
            # 点と、これまで通ってきた頂点を取り出す
            v, route = dq.popleft()
            # これまで通ってきた頂点集合と、行き先の頂点集合の積集合をとる
            s = route & edges[v]
            # s=={start}でなければuとおr sが空集合でも通る。sが何やらいろいろあると、通れない。
            if not (not s or s == {start}):
                continue
            for dest in edges[v]:
                # startに戻ってきたら出力して終了
                if dest == start:
                    print(len(route))
                    print(*route, sep='\n')
                    return
                # 訪問済みであれば、スルー
                if visited[dest]:
                    continue
                visited[dest] = 1
                # destを始点として、通ってきた頂点にdestを追加したもの
                dq.append((dest, route | {dest}))

    print(-1)


def __starting_point():
    solve()

__starting_point()

import sys
from collections import deque
N, M = map(int, input().split())
edges = [[] for i in range(N)]
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    AB.append((a-1, b-1))
def BFS(s):
    prev = [-1]*N
    que = deque([s])
    while que:
        v = que.pop()
        for nv in edges[v]:
            if nv == s:
                prev[nv] = v
                return (s, prev)
            if prev[nv]<0:
                que.append(nv)
                prev[nv] = v
    return (-1, prev)
for v in range(N):
    v0, prev = BFS(v)
    if v0>=0:
        break
if v0<0:
    print(-1)
    return
circle = set()
circle.add(v0)
pv = prev[v0]
while pv != v0:
    circle.add(pv)
    pv = prev[pv]
for a, b in AB:
    if a in circle and b in circle and prev[b] != a:
        pv = prev[b]
        while pv != a:
            circle.remove(pv)
            pv = prev[pv]
        prev[b] = a
print(len(circle))
for i in circle:
    print(i+1)

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)

from collections import*
n,m=map(int,input().split())
outs=defaultdict(list)
ins=defaultdict(int)
for _ in range(m):
    a,b=map(int,input().split())
    outs[a-1]+=b-1,
    ins[b-1]+=1
q=deque(i for i in range(n)if ins[i]==0)
res=[]
while q:
    v=q.popleft()
    res+=v,
    for w in outs[v]:
        ins[w]-=1
        if ins[w]==0:
            q.append(w)
print(-(len(res)==n))

import sys

stdin = sys.stdin

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

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


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

import sys
from collections import deque


def shave(fwd_link, bwd_link):
    # Vertices having no leaving link
    q = [v for v, links in enumerate(fwd_link) if not links]
    while q:
        v = q.pop()
        for u in bwd_link[v]:
            fwd_link[u].remove(v)
            if not fwd_link[u]:
                q.append(u)
    # Vertices having no entering link
    q = [v for v, links in enumerate(bwd_link) if not links]
    while q:
        v = q.pop()
        for u in fwd_link[v]:
            bwd_link[u].remove(v)
            if not bwd_link[u]:
                q.append(u)


def bfs(s, fwd_link):
    predecessors = [-1] * n
    q = deque()
    for v in fwd_link[s]:
        predecessors[v] = s
        q.append((v, s))
    visited = set()
    while q:
        v, p = q.popleft()
        if v in visited:
            continue
        visited.add(v)
        predecessors[v] = p

        if v == s:
            break

        for u in fwd_link[v]:
            if u not in visited:
                q.append((u, v))

    circuit = {s}
    v = predecessors[s]
    while v != s:
        circuit.add(v)
        v = predecessors[v]

    return predecessors, circuit


def check(predecessors, circuit, fwd_link):
    for v in circuit:
        fwd_link[v].intersection_update(circuit)
        if len(fwd_link[v]) == 1:
            continue
        for u in fwd_link[v]:
            if predecessors[u] != v:
                return u
    return -1


def print_ans(circuit):
    print((len(circuit)))
    print((*(v + 1 for v in circuit)))


def solve(fwd_link, bwd_link):
    shave(fwd_link, bwd_link)
    s = -1
    for s, (f, b) in enumerate(zip(fwd_link, bwd_link)):
        if f and b:
            break
    else:
        print((-1))
        return

    while True:
        predecessors, circuit = bfs(s, fwd_link)
        res = check(predecessors, circuit, fwd_link)
        if res == -1:
            print_ans(circuit)
            break
        s = res


n, m = list(map(int, input().split()))
fwd_link = [set() for _ in range(n)]
bwd_link = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = list(map(int, line.split()))
    a -= 1
    b -= 1
    fwd_link[a].add(b)
    bwd_link[b].add(a)

solve(fwd_link, bwd_link)


# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def SCC(N, edges):
    """ 強連結成分分解 """

    nodes1 = [[] for i in range(N)]
    nodes2 = [[] for i in range(N)]
    for u, v in edges:
        nodes1[u].append(v)
        nodes2[v].append(u)

    T = []
    visited = [False] * N
    def rec1(cur):
        visited[cur] = True
        for nxt in nodes1[cur]:
            if not visited[nxt]:
                rec1(nxt)
        # 行き止まったところから順にTに入れていく
        T.append(cur)

    # グラフが連結とは限らないので全頂点やる
    for u in range(N):
        if not visited[u]:
            rec1(u)

    visited = [False] * N
    group = [0] * N
    grpcnt = 0
    def rec2(cur):
        group[cur] = grpcnt
        visited[cur] = True
        for nxt in nodes2[cur]:
            if not visited[nxt]:
                rec2(nxt)

    # 逆順で進めるところまで行く
    for u in reversed(T):
        if not visited[u]:
            rec2(u)
            grpcnt += 1
    return grpcnt, group

def bfs(N, nodes, src):
    """ BFS(一般グラフ、重みなし) """
    from collections import deque

    que = deque([(src, -1, 0)])
    dist = [()] * N
    mn = INF
    end = -1
    while que:
        u, prev, c = que.popleft()
        # 同じ強連結成分内のみでやる
        if group[u] != group[src]:
            continue
        if dist[u]:
            # 訪問済で始点に帰ってきたら、最短チェック
            if u == src:
                if c < mn:
                    mn = c
                    end = prev
            continue
        dist[u] = (c, prev)
        for v in nodes[u]:
            que.append((v, u, c+1))
    # 経路、始点に戻ってくる最短距離、その直前の頂点を返す
    return dist, mn, end

def get_route(s, t, res):
    """ s,t間の経路を取得 """
    prev = t
    StoT = [t]
    while prev != s:
        prev = res[prev][1]
        if prev == -1:
            return None
        StoT.append(prev)
    StoT = StoT[::-1]
    return StoT

N, M = MAP()
nodes = [[] for i in range(N)]
edges = []
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    edges.append((a, b))

# 強連結成分毎に見る
grpcnt, group = SCC(N, edges)
ans = INF
for i in range(N):
    # 経路、始点に戻ってくる最短距離、その直前の頂点
    dist, mn, end = bfs(N, nodes, i)
    if mn < ans:
        ans = mn
        route = get_route(i, end, dist)
if ans != INF:
    print(ans)
    [print(u + 1) for u in route]
else:
    # そもそも閉路なし
    print(-1)


from collections import deque

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

ans = []
for sta in range(N):
    prev = [-1] * N
    que = deque([sta])

    while que:
        v = que.popleft()
        for w in edge[v]:
            if w == sta: # 閉路発見
                path = []
                while v != -1:
                    path.append(v+1)
                    v = prev[v]
                if (not ans) or (len(ans) > len(path)):
                    ans = path
                break

            if prev[w] != -1: continue

            prev[w] = v
            que.append(w)

if ans:
    print(len(ans))
    print(*ans, sep='\n')
else:
    print(-1)

import sys
sys.setrecursionlimit(10**4)
def input():
	return sys.stdin.readline()[:-1]

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

seen = [False for _ in range(n)]
visited = [False for _ in range(n)]
begin = -1
hist = []

def dfs(x):
	nonlocal begin, hist
	if begin >= 0:
		return
	seen[x] = True
	hist.append(x)
	for v in adj[x]:
		if visited[v]:
			continue
		if seen[v] == True and visited[v] == False:
			begin = v
			return
		dfs(v)
		if begin >= 0:
			return
	visited[x] = True
	hist.pop()
	return

for i in range(n):
	if begin < 0:
		dfs(i)
	if begin >= 0:
		break

if begin < 0:
	print(-1)
	return
else:
	cycle = []
	included = [False for _ in range(n)]
	included[begin] = True
	while hist and hist[-1] != begin:
		cycle.append(hist[-1])
		included[hist[-1]] = True
		hist.pop()
	cycle.append(begin)
	hist.pop()

	while True:
		meets = True
		l = len(cycle)
		ind = [-1 for _ in range(n)]
		for i in range(l):
			ind[cycle[i]] = i
		for i in range(l):
			if meets == False:
				break
			for v in adj[cycle[(i+1)%l]]:
				if included[v] == True and v != cycle[i]:
					meets = False
					new_start_id, new_end_id = ind[v], (i+1)%l
					break

		if meets:
			print(len(cycle))
			print(*[c+1 for c in cycle], sep="\n")
			break
		else:
			new_cycle = []
			included = [False for _ in range(n)]
			cur = new_end_id
			while cur != new_start_id:
				new_cycle.append(cycle[cur])
				included[cycle[cur]] = True
				cur = (cur+1)%l
			new_cycle.append(cycle[new_start_id])
			cycle = new_cycle

import sys
from collections import deque
input = sys.stdin.readline

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

dist = [[-1] * n for _ in range(n)]
for i in range(n):
    queue = deque([(i, 0)])
    while queue:
        v, c = queue.popleft()
        for v_next in graph[v]:
            if dist[i][v_next] == -1:
                dist[i][v_next] = c + 1
                queue.append((v_next, c+1))

# print(dist)
ans_len = n + 1
for i in range(n):
    if dist[i][i] != -1:
        ans_len = min(ans_len, dist[i][i])
if ans_len == n + 1:
    print(-1)
else:
    for i in range(n):
        if dist[i][i] == ans_len:
            start_v = i
            break

    dist = [-1] * n
    prev_v = [-1] * n
    queue = deque([(start_v, 0)])
    while queue:
        v, c = queue.popleft()
        if v == start_v and c != 0:
            break
        for v_next in graph[v]:
            if dist[v_next] == -1:
                dist[v_next] = c + 1
                prev_v[v_next] = v
                queue.append((v_next, c+1))

    ans = []
    # print(start_v)
    # print(dist)
    # print(prev_v)
    v = start_v
    for i in range(ans_len):
        ans.append(v+1)
        v = prev_v[v]

    print(ans_len)
    print(*ans, sep='\n')


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)

from collections import deque

n,m = map(int,input().split())
g = [list() for _ in range(n+1)]
en = [0]*(n+1)
for _ in range(m):
  u,v = map(int,input().split())
  g[u].append(v)
  en[v] += 1
q = deque(i for i in range(1,n+1) if en[i] == 0)
done = list()
while q:
  v = q.popleft()
  for x in g[v]:
    en[x] -= 1
    if not en[x]:
      q.append(x)
  done.append(v)
print(-1 if len(done) == n else 0)

import sys
from collections import defaultdict

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

def main():
    def bfs(u):
        dist = [inf] * n
        cur = [u]
        pre = [-1] * n
        dist[u] = 0
        d = 0
        while cur:
            d += 1
            nxt = []
            for v in cur:
                for kv in to[v]:
                    if dist[kv] != inf: continue
                    dist[kv] = d
                    pre[kv] = v
                    nxt.append(kv)
            cur = nxt
        mn = [inf, -1]
        for v in range(n):
            if v == u: continue
            if u in to[v]:
                mn = min(mn, [dist[v], v])

        # print(dist)
        # print(mn)
        # print(pre)
        res = []
        v = mn[1]
        if mn[0] == inf:
            return [0] * (n + 1)
        for _ in range(mn[0] + 1):
            res.append(v)
            v = pre[v]
        return res

    inf = 10 ** 9
    n, m = list(map(int, input().split()))
    to = defaultdict(set)
    for _ in range(m):
        u, v = list(map(int, input().split()))
        to[u - 1].add(v - 1)
    ans = [0] * (n + 1)
    for u in range(n):
        res = bfs(u)
        if len(res) < len(ans):
            ans = res
    if len(ans) == n + 1:
        print((-1))
    else:
        print((len(ans)))
        for u in ans:
            print((u + 1))

main()


from collections import*
n,m,*t=list(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)))


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 = 頂点数, サイクル最後の頂点、で持つ
    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)
    return
else:
    ans_num = cycle_num
    ans_list = jisho[kouho_v]
    print(cycle_num)
    print(*ans_list, sep="\n")


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

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

from collections import deque

mindist = N
ans = None
for g in range(N):
    for s in es[g]:
        q = deque([s])
        dist = [N]*N
        dist[s] = 0
        prev = [-1]*N
        while q:
            v = q.popleft()
            if v==g:
                break
            for to in es[v]:
                if dist[to] <= dist[v] + 1: continue
                dist[to] = dist[v] + 1
                prev[to] = v
                q.append(to)
        else:
            continue
        if dist[g] >= mindist: continue
        mindist = dist[g]
        v = g
        tmp = [v+1]
        while prev[v] >= 0:
            v = prev[v]
            tmp.append(v+1)
        ans = tmp

if ans:
    print(len(ans))
    print(*ans, sep='\n')
else:
    print(-1)

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

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)

from collections import deque

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

ans = []
for sta in range(N):
    prev = [-1] * N
    que = deque([sta])

    while que:
        v = que.popleft()
        for w in edge[v]:
            if w == sta:
                path = []
                while v != -1:
                    path.append(v+1)
                    v = prev[v]
                if (not ans) or (len(ans) > len(path)):
                    ans = path
                break

            if prev[w] != -1: continue

            prev[w] = v
            que.append(w)

if ans:
    print(len(ans))
    print(*ans, sep='\n')
else:
    print(-1)


from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
	a,b=map(int,input().split())
	G[a-1].append(b-1)
deg=[0 for i in range(N)]
for i in range(N):
	for p in G[i]:
		deg[p]+=1
q=deque(i for i in range(N) if deg[i]==0)
res=[]
while q:
	u=q.popleft()
	res.append(u)
	for v in G[u]:
		deg[v]-=1
		if deg[v]==0:
			q.append(v)
if len(res)==N:
	print(-1)
	return
X={i for i in range(N)}
for st in range(N):
	pre=[-1 for i in range(N)]
	q=deque([st])
	flag=0
	while(q):
		r=q.popleft()
		for p in G[r]:
			if pre[p]==-1:
				pre[p]=r
				q.append(p)
			if pre[st]!=-1:
				Y={st}
				tmp=pre[st]
				while(tmp!=st):
					Y.add(tmp)
					tmp=pre[tmp]
				if len(Y)<len(X):
					X={i for i in Y}
				flag=1
				break
		if flag:
			break
print(len(X))
for i in X:
	print(i+1)

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

from collections import deque

d = N+1
flag = False
for i in range(N):
    for v in E[i]:
        q = deque()
        q.append(v)
        used = [N+1]*N
        used[v] = 1
        while q:
            temp = q.popleft()
            if used[temp] > d:
                break
            for u in E[temp]:
                if u == i and d > used[temp]+1:
                    d = used[temp]+1
                    memo = [temp, u]
                    q = deque()
                    flag = True
                    break
                elif u == i:
                    q = deque()
                    break
                if used[u] < N+1:
                    continue
                used[u] = used[temp]+1
                q.append(u)

import heapq
if flag:
    h = []
    dist = [N+1]*N
    dist[memo[1]] = 0
    for v in E[memo[1]]:
        heapq.heappush(h, (1, v))
    while True:
        temp = heapq.heappop(h)
        if dist[temp[1]] < N+1:
            continue
        dist[temp[1]] = temp[0]
        if temp[1] == memo[0]:
            break
        for v in E[temp[1]]:
            if dist[v] < N+1:
                continue
            heapq.heappush(h, (temp[0]+1, v))
    ans = [memo[0]]
    d = dist[memo[0]]-1
    prev = memo[0]
    while d >= 0:
        for i in range(N):
            if dist[i] == d and prev in E[i]:
                prev = i
                ans.append(i)
                d -= 1
                break
    print(len(ans))
    for i in ans:
        print(i+1)
else:
    print(-1)

from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    print(0)
    print()
    return

    loopStart = L[-1]
    while L[0] != loopStart:
        L.popleft()

    print(len(L) - 1)
    ans = [v + 1 for v in L]
    print(*ans[: -1], sep='\n')
    return

print(-1)

def f_pure():
    # 参考: http://drken1215.hatenablog.com/entry/2019/09/29/012000
    from collections import deque
    N, M = [int(i) for i in input().split()]

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

    shortest = N + 1
    ans = []
    for s in range(N):
        # 頂点sから他の辺へ行くには何個の頂点を辿る必要があるか計算する
        dist = [-1] * N
        previous = [-1] * N  # [n]: 頂点nへはどこから来たか
        queue = deque([s])
        dist[s] = 0
        while queue:
            v = queue.pop()
            for next_node in graph[v]:
                if dist[next_node] == -1:
                    dist[next_node] = dist[v] + 1
                    previous[next_node] = v
                    queue.appendleft(next_node)

        for t in range(N):
            if t == s or dist[t] == -1:
                continue  # 頂点tは始点と同じ、または、始点から到達不可能
            for next_node in graph[t]:
                if next_node == s:  # ループ完成
                    ans_tmp = [s]  # 解になりうる頂点集合
                    current_node = t
                    # 頂点tからsまで巻き戻していく
                    while current_node != s:
                        ans_tmp.append(current_node)
                        current_node = previous[current_node]
                    # 頂点集合の濃度が減少した
                    if shortest > len(ans_tmp):
                        shortest = len(ans_tmp)
                        ans = ans_tmp

    if shortest == N + 1:
        return -1  # 閉路がなかった。条件を満たす頂点集合はない
    return ' '.join(map(str, [len(ans)] + sorted(v + 1 for v in ans)))

print(f_pure())

from collections import deque

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

edges = [[] for _ in range(N)]
edgesR = [[] for _ in range(N)]

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edgesR[to].append(fr)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    loopStart = L.pop()
    while L[0] != loopStart:
        L.popleft()
    V = set(L)
    dist = [float('inf')] * N
    que = deque([(loopStart, 0)])

    while que:
        now, d = que.popleft()

        if dist[now] <= d:
            if now == loopStart:
                dist[loopStart] = d
                break
            continue
        dist[now] = d

        for to in edges[now]:
            if to in V:
                que.append((to, d + 1))

    ans = [loopStart]
    now = loopStart
    while dist[now] > 1:
        for back in edgesR[now]:
            if dist[now] - 1 == dist[back]:
                ans.append(back)
                now = back
                break

    ans = set([a + 1 for a in ans])
    print(len(ans))
    print(*ans, sep='\n')
    return

print(-1)

import sys
sys.setrecursionlimit(10**7)
n,m=list(map(int,input().split()))
g=[[] for _ in range(n)]
for _ in range(m):
  u,v=list(map(int,input().split()))
  u,v=u-1,v-1
  g[u].append(v)
mi=set(range(n))
flg=False
def func(path):
  chk=set(path)
  if len(path)!=2:
    for i,v in enumerate(path):
      nvs=[nv for nv in g[v] if nv in chk]
      if len(nvs)==1:continue
      for nv in nvs:
        if nv==path[(i+1)%len(path)]:continue
        ary=[nv]
        for j,vj in enumerate(path):
          if vj==nv:break
        if i>j:
          ary=path[j:i+1]
        else:
          ary=path[:i+1]+path[j:]
        #print(path,ary,i,j)
        func(ary)
  print((len(path)))
  for v in path:
    print((v+1))
  return

def dfs(v,seen):
  mi.discard(v)
  for nv in g[v]:
    if seen[nv]!=-1:# 巡回閉路
      seen[nv]=v
      path=[v]
      chk={v}
      while seen[v] not in chk:
        v=seen[v]
        path.append(v)
        chk.add(v)
      path.reverse()
      func(path)
    else:
      seen[nv]=v
      dfs(nv,seen)
      seen[nv]=-1
while mi:
  v=mi.pop()
  seen=[-1]*n
  dfs(v,seen)
print((-1))
return


import sys
sys.setrecursionlimit(10**7)

def main():
    N, M = list(map(int, input().split()))
    V = [[] for _ in range(N)]
    for _ in range(M):
        a, b = list(map(int, input().split()))
        V[a - 1].append(b - 1)
    C = [0] * N
    def dfs(n):
        if C[n] == 2:
            return False
        if C[n] == 1:
            return True
        C[n] = 1
        for i in V[n]:
            if dfs(i):
                return True
        C[n] = 2
        return False
    for i in range(N):
        if dfs(i):
            return 0
    return -1
print((main()))


import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    es[a].append(b)
ansr, ansd = -1, INF
for r in range(1, N+1):
    d = [INF] * (N+1)
    d[0] = 0
    dq = deque()
    for w in es[r]:
        dq.append(w)
        d[w] = 1
    while len(dq) > 0:
        v = dq.popleft()
        if v == r:
            break
        nd = d[v]+1
        for u in es[v]:
            if nd < d[u]:
                d[u] = nd
                dq.append(u)
    if d[r] < ansd:
        ansd = d[r]
        ansr = r
if ansr == -1:
    print(-1)
else:
    vis = [0] * (N+1)
    vis[0] = 1
    p = [-1] * (N+1)
    dq = deque()
    for v in es[ansr]:
        vis[v] = 1
        p[v] = 0
        dq.append(v)
    while len(dq) > 0:
        v = dq.popleft()
        if v == ansr:
            break
        for u in es[v]:
            if vis[u] == 0:
                vis[u] = 1
                p[u] = v
                dq.append(u)
    lst = []
    v = ansr
    while p[v] != -1:
        lst.append(v)
        v = p[v]
    print(len(lst))
    print(*lst, sep = '\n')


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

def shorten_cycle(G, route):
    # ループだとすでに分かってるルートに対して、
    # ショートカットが存在する場合はショートカットを行い、
    # ルートを短くする

    _next = {k: v for k, v in zip(route, route[1:]+route[:1])}
    v = route[0]
    while True:
        # もしvからroute内の、次の点ではない点nにいける場合
        for n in G[v]:
            # v -> x -> y -> n としていたところを、
            # v -> n とする
            if n in route and n != _next[v]:
                new_route = [n]
                s = n
                while s != v:
                    s = _next[s]
                    new_route.append(s)
                _next[v] = n
                # 無駄な部分を削除した新しい経路に対して、調査を最初からやり直す
                route = new_route
                v = route[0]
                break
        # 点vにショートカットがない場合
        else:
            # 次の点が最初の点の場合は、もうこれ以上ショートカットできないので終わり
            v = _next[v]
            if v == route[0]:
                break
    
    return route

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

    ans_last = None # sからループを探して見つかった時の、ループの最後の頂点番号
    dq.append(s)
    # BFSでループを見つける
    while dq and ans_last is None:
        v = dq.popleft()
        d = dist[v]
        for n in G[v]:
            # 頂点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))
    
    # 見つからなかった場合はNoneを返す
    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)

    # すべての頂点の入次数が 1、出次数が 1 であるような G の誘導部分グラフ
    # [すべての頂点の入次数が 1、出次数が 1 のグラフ] -> ループ

    # 有向グラフ G=(V,E) に対し、次のような条件を満たす有向グラフ G′=(V′,E′) を G の誘導部分グラフと呼ぶ。
    # V′ は V の (空でない) 部分集合である。
    # E′ は、E の辺であって両端点がともに V′ に含まれるものすべてを含む集合である。

    # -> ループでも、ショートカットできるようなループはだめ

    # 例: 1 -> 2 -> 3 -> 4 -> 5
    #     ^    |         ^    |
    #     |    ----------|    |
    #     ---------------------
    # V' = {1, 2, 3, 4, 5} としてしまうと、
    # E' = {(1->2), (2->3), (3->4), (2->4), (4->5), (5->1)}
    # となってしまい、この誘導部分グラフG'=(V', E')において、
    # 頂点2の出次数が2になってしまう。（頂点4の入次数も2になってしまう）
    # V' = {1, 2, 4, 5} とすれば、
    # E' = {(1->2), (2->4), (4->5), (5->1)}
    # となり、すべての頂点の入次数が 1、出次数が 1 となる
    
    # つまり、ショートカットできない最短のループを1つでも見つければよい
    
    min_route = None
    for s in range(1, N+1):
        # 各頂点を開始点にしてループを探す
        route = find_cycle(G, s)
        # ループが見つかった場合、そこからショートカットできる経路を探して終了
        if route:
            min_route = shorten_cycle(G, route)
            break
    
    if min_route:
        print(len(min_route), *min_route, sep='\n')
    else:
        print(-1)

def __starting_point():
    main()
__starting_point()

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

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


def get_first_cycle(n, edges):
    seen = [-1] * n  # seen: -1: 未確認, 0: 非cycleのnode, 1: cycle候補
    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))
    return

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


import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = list(map(int, read().split()))
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)

    ans = []
    for i in range(N):
        queue = deque([i])
        dist = [-1] * N
        dist[i] = 0
        prev = [-1] * N
        while queue:
            v = queue.popleft()
            for nv in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    prev[nv] = v
                    queue.append(nv)
        for j in range(N):
            if i == j or dist[j] == -1 or i not in G[j]:
                continue
            tmp = []
            k = j
            while k != -1:
                tmp.append(k)
                k = prev[k]

            if not ans or len(ans) > len(tmp):
                ans = tmp

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

    return


def __starting_point():
    main()

__starting_point()

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

from collections import deque
mindist = N
opt = None
for g,tos in enumerate(es):
    for s in tos:
        q = deque([(s,0)])
        prev = [-1]*N
        dist = [N]*N
        dist[s] = 0
        while q:
            v,d = q.popleft()
            for to in es[v]:
                if to==g: break
                if d+1 >= dist[to]: continue
                dist[to] = d+1
                prev[to] = v
                q.append((to,d+1))
            else:
                continue
            break
        else:
            continue
        if d+1 >= mindist: continue
        mindist = d+1
        opt = [g,v]
        while prev[opt[-1]] >= 0:
            opt.append(prev[opt[-1]])
if opt:
    ans = [o+1 for o in opt]
    print(len(ans))
    print(*ans, sep='\n')
else:
    print(-1)

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

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

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)

# とりあえず1つサイクルを見つける
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]

# 辺を1つ追加しながら、小さいサイクルを見つける
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')



from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq
sys.setrecursionlimit(100000)

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return list(map(int, input().split())) 
    else: return list(map(int, input().split(sep)))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

compo = []
cs = []
N = 0
M = 0
A = None
B = None
E = None

def main():
    nonlocal compo,cs,N,M,A,B,E
    N, M = rip()
    A = [0] * M
    B = [0] * M
    for i in range(M):
        A[i], B[i] = rip()
        A[i] -= 1
        B[i] -= 1
    
    E = [[] for i in range(N)]
    for i in range(M):
        E[A[i]].append(B[i])
    
    compo = [-1] * N

    def dfs(cmp, route, hs):
        nonlocal compo,cs,N,M,A,B,E
        if(len(cs) > 0) : return
        now = route[len(route) - 1]
        for nxt in E[now]:
            if compo[nxt] == -1:
                compo[nxt] = cmp
                route.append(nxt)
                hs.add(nxt)
                dfs(cmp, route, hs)
                hs.remove(nxt)
                route.pop(-1)
            elif compo[nxt] == cmp:
                if nxt in hs:
                    cs = route[route.index(nxt):]
                return
            else:
                return


    cs = []
    c = 0
    for i in range(N):
        if(compo[i] != -1): continue
        c += 1
        a = []
        hs = set()
        a.append(i)
        hs.add(i)
        compo[i] = c
        dfs(c, a, hs)

    if len(cs) == 0:
        print((-1))
        return
    
    l = cs
    while(True):
        di = dict()
        for i in range(len(l)):
            di[l[i]] = l[(i + 1) % len(l)]
        edx = -1
        for i in range(M):
            if A[i] in di and B[i] in di:
                if di[A[i]] != B[i]:
                    edx = i
                    break
        
        if edx == -1:
            print((len(l)))
            print(("\n".join([str(n + 1) for n in l])))
            return
        
        di[A[edx]] = B[edx]
        nl = [A[edx], B[edx]]
        while True:
            nxt = di[nl[-1]]
            if nxt != nl[0]:
                nl.append(nxt)
            else:
                break
        l = nl

def __starting_point():
    main()

__starting_point()

def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*m]
    g=[set() for _ in [0]*n]
    g2=[set() for _ in [0]*n]
    [g[a-1].add(b-1) for a,b in ab]
    [g2[b-1].add(a-1) for a,b in ab]

    def bfs(start,graph):
        temp=[[start,{start}]]
        while temp:
            temp2=[]
            for j,k in temp:
                for i in graph[j]:
                    if i in k:
                        return j,k
                    else:
                        temp2.append([i,k|{i}])
            temp=temp2
        return None,None

    return_set_pre=set(range(n))
    for i in range(n):
        now,return_set=bfs(i,g)
        if return_set!=None:
            break
    if return_set==None:
        print(-1)
        return 0
    while True:
        for i in return_set_pre-return_set:
            g[i]={}
            g2[i]={}
        for i in return_set:
            g[i]=g[i]&return_set
            g2[i]=g2[i]&return_set
        l1=len([1 for i in range(n) if len(g[i])==1])
        l2=len([1 for i in range(n) if len(g2[i])==1])
        l=len(return_set)
        if l==l1 and l==l2:
            break
        return_set_pre=return_set
        now,return_set=bfs(now,g2)
        for i in return_set_pre-return_set:
            g[i]={}
            g2[i]={}
        for i in return_set:
            g[i]=g[i]&return_set
            g2[i]=g2[i]&return_set
        l1=len([1 for i in range(n) if len(g[i])==1])
        l2=len([1 for i in range(n) if len(g2[i])==1])
        l=len(return_set)
        if l==l1 and l==l2:
            break
        return_set_pre=return_set
        now,return_set=bfs(now,g)
    print(len(return_set))
    for i in return_set:
        print(i+1)
main()

import sys
input = sys.stdin.readline

N, M = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = list(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)    


import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
cand1=set()
cand2=set()
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  cand1.add(a)
  cand2.add(b)
cand=cand1&cand2
ans=-1
for i in range(1,n+1):
  if i not in cand:
    continue
  else:
    q=collections.deque()
    q.append((i,[i]))
    checked=[0]*(n+1)
    while len(q)!=0:
      v,chain=q.popleft()
      if v==i and len(chain)!=1:
        ans=chain[:-1]
      for u in g[v]:
        if u not in cand:
          continue
        elif checked[u]==0:
          checked[u]=1
          q.append((u,chain+[u]))
    cand.discard(i)
if ans==-1:
  print(ans)
else:
  print(len(ans))
  for v in ans:
    print(v)

from collections import*
n,m,*t=map(int,open(0).read().split())
i,o=[0]*n,[[]for _ in range(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)
r=[]
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))

# -*- coding: utf-8 -*-
"""
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())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
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)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    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)
    
    #print("Let's BFS (", n, " times)")
    while len(opnd) != 0:

        #print("clsd: ", clsd)
        #print("opnd: ", opnd)
        
        now = opnd.popleft()
        clsd.add(now)
        
        for e in E[now]:
            if e in clsd:
                if e == n:
                    res = [now]
                    #print("root: ", root)
                    #print("d_list: ", d_list)
                    dist = d_list[now] + 1
                    while len(res) != dist:
                        #   print(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))
        
                
            
            
                

    
def __starting_point():
    main()

__starting_point()

from collections import*
n,m=map(int,input().split())
outs=defaultdict(list)
ins=defaultdict(int)
for _ in range(m):
    a,b=map(int,input().split())
    outs[a-1]+=b-1,
    ins[b-1]+=1
q=deque(i for i in range(n)if ins[i]==0)
res=[]
while q:
    v=q.popleft()
    res+=v,
    for w in outs[v]:
        ins[w]-=1
        if ins[w]==0:
            q.append(w)
print(-(len(res)==n))

import sys
input = sys.stdin.readline

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

EIN=[0]*N
EOUT=[0]*N

EINLIST=[[] for i in range(N)]
EOUTLIST=[[] for i in range(N)]

for i in range(M):
    x,y=list(map(int,input().split()))
    x-=1
    y-=1

    EOUT[x]+=1
    EIN[y]+=1

    EOUTLIST[x].append(y)
    EINLIST[y].append(x)

from collections import deque

Q=deque()
USE=[1]*N

for i in range(N):
    if EIN[i]==0 or EOUT[i]==0:
        Q.append(i)
        USE[i]=0

while Q:
    x=Q.pop()

    for to in EOUTLIST[x]:
        if USE[to]==0:
            continue
        EIN[to]-=1
        if EIN[to]==0:
            Q.append(to)
            USE[to]=0

    for fr in EINLIST[x]:
        if USE[fr]==0:
            continue
        EOUT[fr]-=1
        if EOUT[fr]==0:
            Q.append(fr)
            USE[fr]=0
            
def loopfind():
    for i in range(N):
        if USE[i]==1:
            break
    else:
        return []
    
    Q=deque()
    Q.append(i)
    USESET={i}
    ANS=[i]

    while True:
        for to in EOUTLIST[ANS[-1]]:
            if USE[to]==1:
                nextv=to
                break

        if nextv in USESET:
            break
        else:
            ANS.append(nextv)
            USESET.add(nextv)

    x=ANS.index(nextv)
    return ANS[x:]
        

def shortcut(ANS):
    #print(ANS)

    ANSSET=set(ANS)
    LEN=len(ANS)
    flag=0

    for i in range(LEN):
        for to in EOUTLIST[ANS[i]]:
            if to in ANSSET and ANS[(i+1)%LEN]!=to:
                flag=1
                x=ANS.index(to)

                #print(ANS,i,x)

                break
        if flag:
            break
    #print(flag)

    if flag:
        if x<i:
            return shortcut(ANS[x:i+1])
        else:
            return shortcut(ANS[x:]+ANS[:i+1])

    else:
        return ANS

ANS=shortcut(loopfind())
if len(ANS)==0:
    print((-1))
else:
    print((len(ANS)))
    for ans in ANS:
        print((ans+1))
        


import sys
from collections import deque
input = sys.stdin.readline        

def main():

    def loopfind():
        for i in range(N):
            if USE[i]==1:
                break
        else:
            return []
        
        Q=deque()
        Q.append(i)
        USESET={i}
        ANS=[i]

        while True:
            for to in EOUTLIST[ANS[-1]]:
                if USE[to]==1:
                    nextv=to
                    break

            if nextv in USESET:
                break
            else:
                ANS.append(nextv)
                USESET.add(nextv)

        x=ANS.index(nextv)
        return ANS[x:]

    def shortcut(ANS):
        #print(ANS)

        ANSSET=set(ANS)
        LEN=len(ANS)
        flag=0

        for i in range(LEN):
            for to in EOUTLIST[ANS[i]]:
                if to in ANSSET and ANS[(i+1)%LEN]!=to:
                    flag=1
                    x=ANS.index(to)

                    #print(ANS,i,x)

                    break
            if flag:
                break
        #print(flag)

        if flag:
            if x<i:
                return shortcut(ANS[x:i+1])
            else:
                return shortcut(ANS[x:]+ANS[:i+1])

        else:
            return ANS
    
    N,M=map(int,input().split())

    EIN=[0]*N
    EOUT=[0]*N

    EINLIST=[[] for i in range(N)]
    EOUTLIST=[[] for i in range(N)]

    for i in range(M):
        x,y=map(int,input().split())
        x-=1
        y-=1

        EOUT[x]+=1
        EIN[y]+=1

        EOUTLIST[x].append(y)
        EINLIST[y].append(x)

    Q=deque()
    USE=[1]*N

    for i in range(N):
        if EIN[i]==0 or EOUT[i]==0:
            Q.append(i)
            USE[i]=0

    while Q:
        x=Q.pop()

        for to in EOUTLIST[x]:
            if USE[to]==0:
                continue
            EIN[to]-=1
            if EIN[to]==0:
                Q.append(to)
                USE[to]=0

        for fr in EINLIST[x]:
            if USE[fr]==0:
                continue
            EOUT[fr]-=1
            if EOUT[fr]==0:
                Q.append(fr)
                USE[fr]=0

    ANS=shortcut(loopfind())
    if len(ANS)==0:
        print(-1)
    else:
        print(len(ANS))
        for ans in ANS:
            print(ans+1)

main()

#!/usr/bin/env python

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

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

    Ans = [1]*(N+1)
    
    # 全ての頂点から, 閉路が存在しないかを確認する
    for s in range(N):
        prev = [-1]*N
        dist = [-1]*N
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for nv in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    prev[nv] = v
                    dq.append(nv)
                # 次が 0番目(開始地点) なら閉路あり
                if dist[nv] == 0:
                    prev[nv] = v

        # 開始地点の前 が -1でない => 閉路あり
        if prev[s] != -1:
            v = prev[s]
            ans = set()
            for _ in range(max(dist)+1):
                ans.add(prev[v])
                v = prev[v]
            if len(Ans) > len(ans):
                Ans = list(ans)
    
    if len(Ans) == N+1:
        print(-1)
    else:
        print(len(Ans))
        Ans.sort()
        for v in Ans:
            print(v+1)

def __starting_point():
    main()
__starting_point()

import queue

import sys
sys.setrecursionlimit(10000)

N, M = map(int, input().split())
S = set(range(N))

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

visit = [0] * N
def DFS(p, n):
    if visit[p] != 0:
        return visit[p]
    else:
        visit[p] = n + 1
        for i in to[p]:
            r = DFS(i, n + 1)
            if r > 0:
                return r
        visit[p] = -1
        return -1

for i in range(N):
    r = DFS(i,0)
    if r > 0:
        for j in range(N):
            if visit[j] < r:
                S.discard(j)
        for j in range(N):
            if j in S:
                for k in to[j]:
                    if k in S:
                        if visit[k] < visit[j]:
                            for l in range(N):
                                if visit[l] < visit[k] or visit[l] > visit[j]:
                                    S.discard(l)
                        else:
                            for l in range(N):
                                if visit[l] > visit[j] and visit[l] < visit[k]:
                                    S.discard(l)
        print(len(S))
        for j in list(S):
            print(j+1)
        break
    if i == N-1:
        print(-1)

from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    loopStart = L.pop()
    while L[0] != loopStart:
        L.popleft()

    ans = []
    K = len(L)
    for i, now in enumerate(L):
        for to in edges[now]:
            if i + 1 >= K or to == L[i + 1]:
                ans.append(now + 1)
                break
        else:
            break
    else:
        print(0)
        print()
        # print(len(ans))
        # print(*ans, sep='\n')
        return

print(-1)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  G[a].append(b)
seen = [False]*n
def dfs(v):
  seen[v] = True
  for nv in G[v]:
    nxt[v] = nv
    if seen[nv]:
      return nv
    s = dfs(nv)
    if s != -1:
      return s
  seen[v] = False
  return -1
for i in range(n):
  nxt = [-1]*n
  s = dfs(i)
  if s != -1:
    break
else:
  print(-1)
  return
while True:
  used = set()
  L = []
  while s not in used:
    used.add(s)
    L.append(s)
    s = nxt[s]
  L.append(s)
  for i in range(len(L)-1):
    a, b = L[i], L[i+1]
    for nv in G[a]:
      if nv != b and nv in used:
        nxt[a] = nv
        s = a
        break
    else:
      continue
    break
  else:
    print(len(used))
    for v in used:
      print(v+1)
    break

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = list(map(int, read().split()))
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)

    def dfs(v, p, seen, finished, hist):
        seen[v] = True
        hist.append(v)
        for nv in G[v]:
            if nv == p:
                continue
            if finished[nv]:
                continue
            if seen[nv] and not finished[nv]:
                return nv

            pos = dfs(nv, v, seen, finished, hist)
            if pos != -1:
                return pos
        hist.pop()
        finished[v] = True
        return -1

    for i in range(N):
        seen = [False] * N
        finished = [False] * N
        hist = []
        pos = dfs(i, -1, seen, finished, hist)
        if pos != -1:
            break

    if pos == -1:
        print((-1))
        return

    cycle = []
    while hist:
        t = hist.pop()
        cycle.append(t)
        if t == pos:
            break

    cycle.reverse()

    while True:
        order = [-1] * N
        for i, v in enumerate(cycle):
            order[v] = i

        for i, v in enumerate(cycle):
            ord_from = ord_to = -1
            for nv in G[v]:
                if v == nv or order[nv] == -1 or order[nv] == (order[v] + 1) % len(cycle):
                    continue
                ord_from, ord_to = i, order[nv]
                break
            if ord_from != -1:
                break

        if ord_from == -1:
            break

        if ord_from < ord_to:
            cycle = cycle[: ord_from + 1] + cycle[ord_to:]
        else:
            cycle = cycle[ord_to : ord_from + 1]

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

    return


def __starting_point():
    main()

__starting_point()

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

#!python3

import sys
sys.setrecursionlimit(10 ** 6)

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

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

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

def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())
e = [[] for _ in range(n)]

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

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            print(-99999)
            return
        else:
            search_path(x, temp + [x])


t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(i, [i])

print(-1)

from collections import deque
import sys

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

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

for i in range(M):

    A,B = list(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] 

    #print (q,now,lasp,nownum)

    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)

                return

    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 (flag,nex,lasp)

print((-1))


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 # sからループを探して見つかった時の、ループの最後の頂点番号
    dq.append(s)
    # BFSで、最短のループを見つける
    while dq and ans_last is None:
        v = dq.popleft()
        d = dist[v]
        for n in G[v]:
            # 頂点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))
    
    # 見つからなかった場合はNoneを返す
    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)

    # すべての頂点の入次数が 1、出次数が 1 であるような G の誘導部分グラフ
    # [すべての頂点の入次数が 1、出次数が 1 のグラフ] -> ループ

    # 有向グラフ G=(V,E) に対し、次のような条件を満たす有向グラフ G′=(V′,E′) を G の誘導部分グラフと呼ぶ。
    # V′ は V の (空でない) 部分集合である。
    # E′ は、E の辺であって両端点がともに V′ に含まれるものすべてを含む集合である。

    # -> ループでも、ショートカットできるようなループはだめ

    # 例: 1 -> 2 -> 3 -> 4 -> 5
    #     ^    |         ^    |
    #     |    ----------|    |
    #     ---------------------
    # V' = {1, 2, 3, 4, 5} としてしまうと、
    # E' = {(1->2), (2->3), (3->4), (2->4), (4->5), (5->1)}
    # となってしまい、この誘導部分グラフG'=(V', E')において、
    # 頂点2の出次数が2になってしまう。（頂点4の入次数も2になってしまう）
    # V' = {1, 2, 4, 5} とすれば、
    # E' = {(1->2), (2->4), (4->5), (5->1)}
    # となり、すべての頂点の入次数が 1、出次数が 1 となる
    
    # つまり、ショートカットできない最短のループを1つでも見つければよい
    
    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)

def __starting_point():
    main()
__starting_point()

import sys
sys.setrecursionlimit(10**7)

def main():
    N, M = list(map(int, input().split()))
    V = [[] for _ in range(N)]
    for _ in range(M):
        a, b = list(map(int, input().split()))
        V[a - 1].append(b - 1)
    C = [0] * N
    loop = []
    def dfs(n):
        if C[n] == 2:
            return False
        if C[n] == 1:
            loop.append(n)
            return True
        C[n] = 1
        for i in V[n]:
            if dfs(i):
                loop.append(n)
                return True
        C[n] = 2
        return False
    for i in range(N):
        if dfs(i):
            break
    if len(loop) == 0:
        print('-1')
        return
    for i in range(1, len(loop)):
        if loop[i] == loop[0]:
            break
    loop = loop[:i][::-1]

    def minimize(l):
        s = set(l)
        for i in range(len(l)):
            for j in V[l[i]]:
                if j == l[(i + 1) % len(l)]:
                    continue
                if j in s:
                    break
            else:
                continue
            break
        else:
            return l
        I = {m: k for k, m in enumerate(l)}
        j = I[j]
        if i < j:
            l = l[0:i + 1] + l[j:]
        else:
            l = l[j:i + 1]
        return l
    while True:
        t = len(loop)
        loop = minimize(loop)
        if len(loop) == t:
            break
    print(t)
    print(('\n'.join(str(i + 1) for i in loop)))
main()


import sys
import io, os
input = sys.stdin.buffer.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

from collections import deque
INF = 10**18
temp= INF
for a, b in edge:
    q = deque([])
    q.append(b)
    visit = [INF]*n
    visit[b] = 0
    par = [-1]*n
    while q:
        v = q.popleft()
        for u in g[v]:
            if visit[u] == INF:
                visit[u] = visit[v]+1
                par[u] = v
                q.append(u)
    if visit[a]+1 <= temp:
        ans = []
        v = a
        ans.append(v+1)
        while par[v] != -1:
            v = par[v]
            ans.append(v+1)
        temp =  visit[a]+1

if temp == INF:
    print(-1)
else:
    if ans:
        print(len(ans))
        print(*ans, sep='\n')
    else:
        print(-1)


from collections import deque
n,m = list(map(int,input().split()))
path = [set() for _ in range(n)]
pathr= [set() for _ in range(n)]
for _ in range(m):
    a,b = list(map(int,input().split()))
    path[a-1].add(b-1)
    pathr[b-1].add(a-1)

def bfs(start):
    que = deque()
    d = [1e100]*n
    for i in path[start]:
        que.append(i)
        d[i] = 1
    while que:
        p = que.popleft()
        for nxt in path[p]:
            if d[nxt] == 1e100:
                que.append(nxt)
            d[nxt] = min(d[nxt], d[p] + 1)
    if d[start] == 1e100:
        return [0] * (n+1)
    ret = [0]*d[start]
    ret[-1] = start
    now = start
    for i in range(d[start] - 1)[::-1]:
        for p in pathr[now]:
            if d[p] == i+1:
                now = p
                ret[i] = now
                break
    return ret
ans = [0]*(n+1)
for i in range(n):
    tmp = bfs(i)
    if len(ans) > len(tmp):
        ans = tmp
if len(ans) > n:
  print((-1))
else:
    print((len(ans)))
    for i in ans:
        print((i+1))


def find_cycle(N, AB):
  for c in range(N):
    stack = [(c, [])]
    while stack:
      # print("stack:", stack)
      curr, visited = stack.pop()
      if curr in visited:
        # print("cycle found:", curr)
        return visited
      else:
        # print("adding in visited:", curr)
        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)
# print("cycle:", cycle)
if not cycle:
    print(-1)
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print(len(cycle))
    for v in cycle:
        print(v + 1)

import sys
sys.setrecursionlimit(10 ** 7)

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

def main():
    n, m = map(int, input().split())
    G = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        G[a].append(b)
    ans = []
    f = False
    st = set()
    arr = [0]*(n+1)
    for i in range(1, n+1):
        st.add(i)
        if solve(G, i, ans, st, i, arr, 1):
            f = True
            break
        st.remove(i)
    if f:
        print(len(ans))
        ans.sort()
        for v in ans:
            print(v)
    else:
        print(-1)

def __starting_point():
    main()
__starting_point()

N, M = map(int, input().split())
tree = dict(zip(range(1, N+1), [[] for i in range(N)]))
for i in range(M):
  a, b = map(int, input().split())
  tree[a].append(b)


is_visited = [False]*(N+1)
num_visited = 0
def find_cycle(d):
  nonlocal is_visited
  nonlocal num_visited
  cycle = []
  l = 1001
  while d:
    node = d[-1]
    if tree[node]:
      child = tree[node].pop()
      if not is_visited[child]:
        is_visited[child] = True
        num_visited += 1
      if child in cycle and node in cycle:
        idn = cycle.index(node)
        idc = cycle.index(child)
        cycle = cycle[:idn+1] + cycle[idc:]
        l = len(cycle)
      if child in d:
        idx = d.index(child)
        if len(d) - idx < l:
          cycle = d[idx:]
          l = len(cycle)
      else:
        d.append(child)
    else:
      d.pop()
  return cycle


is_visited[0] = True
num_visited += 1
i = 1
while num_visited < N+1:
  while is_visited[i]:
    i += 1
  d = [i]
  is_visited[i] = True
  num_visited += 1
  cycle = find_cycle(d)
  if cycle:
    print(len(cycle))
    print(*cycle, sep='\n')
    return

print(-1)

from collections import deque
N,M=list(map(int,input().split()))
G=[[] for i in range(N)]
for i in range(M):
    a,b=list(map(int,input().split()))
    G[a-1].append(b-1)
K=[0 for i in range(N)]
for i in range(N):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(N) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
if len(res)==N:
    print((-1))
    return
X={i for i in range(N)}
for st in range(N):
    before=[-1 for i in range(N)]
    q=deque([st])
    flag=0
    while(q):
        r=q.popleft()
        for p in G[r]:
            if before[p]==-1:
                before[p]=r
                q.append(p)
            if before[st]!=-1:
                Y={st}
                tmp=before[st]
                while(tmp!=st):
                    Y.add(tmp)
                    tmp=before[tmp]
                if len(Y)<len(X):
                    X={i for i in Y}
                flag=1
                break
        if flag:
            break
print((len(X)))
for i in X:
    print((i+1))


import sys
sys.setrecursionlimit(10 ** 6)

n, m = list(map(int, input().split()))
e = [[] for _ in range(n)]

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

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            print((-99999))
            return
        else:
            search_path(x, temp + [x])


t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(i, [i])

print((-1))


import sys
sys.setrecursionlimit(10**7)
def main():
    N, M = list(map(int, input().split()))
    l = [[] for _ in range(N)]
    for _ in range(M):
        a, b = list(map(int, input().split()))
        l[a-1].append(b-1)
    c = [0] * N
    loop = []
    def cyclic(n):
        if c[n] == 2:
            return False
        if c[n] == 1:
            loop.append(n)
            return True
        c[n] = 1
        for i in l[n]:
            if cyclic(i):
                loop.append(n)
                return True
        c[n] = 2
        return False
    for i in range(N):
        if cyclic(i):
            break
    if len(loop) == 0:
        print((-1))
        return
    loop.reverse()
    t = loop[-1]
    loop = loop[loop.index(t):]
    ll = set(loop)
    flag = True
    while flag:
        for i, v in enumerate(loop[:-1]):
            flag2 = False
            for j in l[v]:
                if j in ll and loop[i + 1] != j:
                    if loop.index(j) == 0:
                        loop = loop[:i+1] + [j]
                    elif loop.index(j) < i:
                        loop = loop[loop.index(j):i+1] + [j]
                    else:
                        loop = loop[:i+1] + loop[loop.index(j):]
                    ll = set(loop)
                    flag2 = True
                    break
            if flag2:
                break
        else:
            flag = False
    loop = set(loop)
    print((len(loop)))
    for i in loop:
        print((i+1))
    return
main()


from collections import deque

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

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

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

loopsize = INF

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

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

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)
#print(graph)

visited=[False]*(N+1)
def dfs(path):
  nonlocal 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)
  return
    
#remove prefix  
for i in range(len(cycle)):
  if cycle[i]==cycle[-1]:
    cycle=cycle[i:]
    break
#print(cycle)

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)
#print(subgraph)    

#visited=[False]*(N+1)
ex_path=[]
def dfs2(path,t):
  nonlocal 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])
    return
    
  #print(u,v,w)
  #w->u
  dfs2([w],u)
  cycle=ex_path+[w]
  #print(cycle)
  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

n,m=list(map(int,input().split()))
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=list(map(int,input().split()))
    u,v=u-1,v-1
    g[u].append(v)

import sys
sys.setrecursionlimit(10**7)

def func(loop):
    sl=set(loop)
    k=len(loop)
    for i in range(k):
        v=loop[i]
        for nv in g[v]:
            if nv not in sl:continue
            if nv==loop[(i+1)%k]:continue
            j=[j for j in range(k) if loop[j]==nv][0]
            if i<j:
                ary=loop[:i+1]+loop[j:]
            else:
                ary=loop[j:i+1]
            func(ary)
    print((len(loop)))
    for x in loop:
        print((x+1))
    return

mi=set(range(n))
def dfs(v,par):
    mi.discard(v)
    for nv in g[v]:
        if par[nv]==-1:
            par[nv]=v
            dfs(nv,par)
            par[nv]=-1
        else:
            loop=[v]
            while v!=nv:
                loop.append(par[v])
                v=par[v]
            loop.reverse()
            func(loop)
while mi:
    v=mi.pop()
    dfs(v,[-1]*n)
print((-1))


def cycle_detection(V, E, s):
    prev = [-1] * len(V)
    stack = [s]
    while stack:
        v = stack.pop()
        for u in E[v]:
            if u == s:
                prev[u] = v
                return (s, prev)
            if prev[u] == -1:
                stack.append(u)
                prev[u] = v
    return (-1, prev)

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

dag = False
for v in range(N):
    s, prev = cycle_detection(V, E, v)
    if s != -1: break
else:
    dag = True

if dag: print(-1)
else:
    # construct a directed cycle
    cycle = set()
    cycle.add(s)
    pv = prev[s]
    while pv != s:
        cycle.add(pv)
        pv = prev[pv]
    # shrink the directed cycle
    for a, b in edges:
        if a in cycle and b in cycle and prev[b] != a:
            pv = prev[b]
            while pv != a:
                cycle.remove(pv)
                pv = prev[pv]
            prev[b] = a
    print(len(cycle))
    print(*[v + 1 for v in cycle], sep='\n')

import sys

read = sys.stdin.read

N, M = list(map(int, input().split()))
if M != 0:
    AB = list(map(int, read().split()))
else:
    print((-1))
    return

graph = [[] for _ in range(N + 1)]
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)


# cycleを少なくとも一つ検出する
def dfs(original_stack):
    checked = [False] * (N + 1)
    while original_stack:
        start = original_stack.pop()
        if checked[start]:
            continue
        checked[start] = True
        stack = [(start, [start])]
        while stack:
            v, route = stack.pop()
            for i in graph[v]:
                if i in route:
                    return route[route.index(i):]
                else:
                    stack.append((i, route + [i]))
                    checked[i] = True


v = dfs([i for i in range(1, N + 1) if graph[i]])
if not v:
    print((-1))
    return

while True:
    v_s = set(v)
    length = len(v)
    for i, (v_i, v_j) in enumerate(zip(v, v[1:] + [v[0]])):
        for j in graph[v_i]:
            if j != v_j and j in v_s:
                idx = v.index(j)
                if i < idx:
                    v = v[:i + 1] + v[idx:]
                else:
                    v = v[idx:i + 1]
                break
        else:
            continue
        break
    else:
        print((len(v)))
        print(('\n'.join(map(str, v))))
        return


def main():
  from collections import deque
  n,m,*t=map(int,open(0).read().split())
  i=[0]*n
  o=[[]for _ in range(n)]
  for a,b in zip(*[iter(t)]*2):
    o[a-1]+=b-1,
    i[b-1]+=1
  q=deque(v for v,f in enumerate(i)if f<1)
  r=[]
  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))
main()

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)))
def __starting_point():
    main()
__starting_point()

from sys import setrecursionlimit
setrecursionlimit(10000)
N, M = list(map(int, input().split()))
table = [[] for _ in range(N)]
for _ in range(M):
    a, b = list(map(int, input().split()))
    table[a-1].append(b-1)

visit = [False] * N
visit2 = [False] * N
g = []


def dfs(v):
    g.append(v)
    if visit[v]:
        return True
    visit[v] = True
    visit2[v] = True
    for u in table[v]:
        if dfs(u):
            return True
    g.pop()
    visit[v] = False
    return False


for i in range(N):
    g = []
    if not visit2[i]:
        if dfs(i):
            break
else:
    print((-1))
    return
print((0))
# ans = [v+1 for v in g[g.index(g[-1]):-1]]
# print(len(ans))
# print(*ans, sep="\n")


from collections import deque
N,M=list(map(int,input().split()))
G=[[] for i in range(N)]
for i in range(M):
    a,b=list(map(int,input().split()))
    G[a-1].append(b-1)
K=[0 for i in range(N)]
for i in range(N):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(N) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
if len(res)==N:
    print((-1))
else:
    print((0))



import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	n,m=MI()
	G=[[] for _ in range(n+1)]

	for _ in range(m):
		a,b=MI()
		G[a].append(b)

	A=[10**5]*(n+1)

	for i in range(1,n+1):
		Q=deque([[i,0]])
		D=[-1]*(n+1)
		while Q:
			#print(Q)
			now,d=Q.popleft()
			if now==i and d>0:
				A[i]=d
				break
			for nx in G[now]:
				if D[nx]==-1:
					D[nx]=d+1
					Q.append([nx,d+1])
	#print(A)

	k=min(A)
	#print(k)

	if k==10**5:
		print(-1)
		return

	s=A.index(k)
	#print(s)

	A=[]
	Q=deque([[s,0]])
	D=[10**5]*(n+1)

	while Q:
		now,d=Q.pop()
		if now==s and d>0:
			break
		if d==k:
			continue
		A.append(now)
		for nx in G[now]:
			if D[nx]>d+1:
				D[nx]=d+1
				Q.append([nx,d+1])
	D[s]=0

	#print(A)
	#print(D)

	ans=[]
	d=k-1
	for i in reversed(A):
		if D[i]==d:
			ans.append(i)
			d-=1

	print(k)
	print(*ans[::-1],sep="\n")










def __starting_point():
	main()

__starting_point()

from collections import deque

N, M, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)

shortest = N + 1
ans = []
for s in range(1, N + 1):
    D = [-1] * (N + 1)
    P = [-1] * (N + 1)

    D[s] = 0
    Q = deque([s])
    while Q:
        p = Q.popleft()
        for c in E[p]:
            if D[c] < 0:
                D[c] = D[p] + 1
                P[c] = p
                Q.append(c)

    for t in range(1, N + 1):
        if t == s or D[t] < 0:
            continue

        for v in E[t]:
            if v != s:
                continue

            T = [s]
            cur = t
            while cur != s:
                T.append(cur)
                cur = P[cur]

            if shortest > len(T):
                shortest = len(T)
                ans = T

if shortest == N + 1:
    print(-1)
else:
    print(len(ans))
    print("\n".join(map(str, ans)))

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

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


import sys
sys.setrecursionlimit(10 ** 6)

n, m = list(map(int, input().split()))
e = [[] for _ in range(n)]

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

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            print((-99999))
            return
        else:
            search_path(x, temp + [x])


t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(i, [i])

print((-1))


import sys
from copy import deepcopy as copy
from collections import deque
input = sys.stdin.readline

def main():
    n, m = list(map(int, input().split()))
    
    tree = [[] for _ in range(n)]
    edge = dict()
    for i in range(m):
        a, b = list(map(int, input().split()))
        tree[a-1].append(b-1)
        edge[(a-1, b-1)] = i+1
    
    ans = 0
    for i in range(n):
        not_yet = deque([i])
        already = [False]*n
        dist = [0]*n
        par = [0]*n
        already[i] = True
        sub = []
        
        while not_yet:
            key = not_yet.popleft()
            for v in tree[key]:
                if already[v]:
                    
                    if v == i:
                        sub = [key+1]
                        now = key
                        while now != i:
                            sub.append(par[now]+1)
                            now = par[now]
                        break
                    continue
                
                not_yet.append(v)
                already[v] = True
                dist[v] = dist[key] + 1
                par[v] = key
            if sub:
                break
            
        if sub:
            if ans:
                if len(ans) > len(sub):
                    ans = copy(sub)
            else:
                ans = copy(sub)
            
        
    if ans:
        print((len(ans)))
        for a in ans:
            print(a)
    else:
        print((-1))
        
    
    
def __starting_point():
    main()

__starting_point()

import sys
sys.setrecursionlimit(10 ** 6)

n, m = list(map(int, input().split()))
e = [[] for _ in range(n)]

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

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            print((-99999))
            return
        else:
            search_path(x, temp + [x])


t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(i, [i])

print((-1))