AtCoder Beginner Contest 142 - Pure

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

Starter code:

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

def find_shortest_cycle(G, s):
	dq = deque()
	N = len(G)
	INF = float('inf')
	dist = [INF] * N
	dist[s] = 0
	parent = [-1] * N
	ans_last = None
	dq.append(s)
	while dq and ans_last is None:
		v = dq.popleft()
		d = dist[v]
		for n in G[v]:
			if dist[n] == 0:
				ans_last = v
				parent[n] = v
				break
			elif dist[n] == INF:
				dist[n] = d + 1
				parent[n] = v
				dq.append(n)
	if ans_last:
		g = ans_last
		route = [g]
		while g != s:
			g = parent[g]
			route.append(g)
		return list(reversed(route))
	return None

def main():
	(N, M, *A) = map(int, read().split())
	G = [[] for i in range(N + 1)]
	for (a, b) in zip(A[::2], A[1::2]):
		G[a].append(b)
	min_route = None
	for s in range(1, N + 1):
		route = find_shortest_cycle(G, s)
		if route:
			if min_route is None or len(route) < len(min_route):
				min_route = route
	if min_route:
		print(len(min_route), *min_route, sep='\n')
	else:
		print(-1)
main()


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


from collections import deque

def main():
	(N, M) = [int(a) for a in input().split()]
	AB = [[int(a) for a in input().split()] for _ in range(M)]
	pp = [[] for _ in range(N)]
	for (a, b) in AB:
		pp[a - 1].append(b - 1)
	startpool = set(range(N))
	result = None
	while len(startpool) != 0:
		start = min(startpool)
		q = deque([(start, [start])])
		renketu = {start}
		while len(q) != 0:
			(p, history) = q.popleft()
			target = pp[p]
			for t in target:
				if t in history:
					if result is None:
						result = history
					elif len(result) > len(history) - history.index(t):
						result = history[history.index(t):]
				if t not in renketu:
					q.append([t, history + [t]])
				renketu.add(t)
		startpool -= renketu
	if result is not None:
		print(len(result))
		for a in result:
			print(a + 1)
		return
	else:
		print(-1)

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


def main():
	import sys
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 7)
	from collections import Counter, deque
	from itertools import combinations, permutations, accumulate, groupby, product
	from bisect import bisect_left, bisect_right
	from heapq import heapify, heappop, heappush
	import math
	(n, m) = map(int, input().split())
	adj = [[] for _ in range(n)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		adj[a - 1].append(b - 1)

	def dfs(s, v):
		for nv in adj[v]:
			if nv == s:
				return [v]
			if visited[nv] == 1:
				continue
			visited[nv] = 1
			res = dfs(s, nv)
			if res != -1:
				res.append(v)
				return res
		return -1
	for s in range(n):
		visited = [0] * n
		visited[s] = 1
		heiro = dfs(s, s)
		if heiro != -1:
			break
	else:
		print(-1)
		exit()
	heiro = heiro[::-1]

	def graph(s, g):
		res = [s]
		d = deque([s])
		for i in range(len(heiro)):
			if heiro[i] == s:
				idx = i
				break
		while d:
			v = d.popleft()
			for nv in adj[v]:
				if visited[nv] == 1 and nv == g:
					res.append(nv)
					return res
			d.append(heiro[idx + 1])
			res.append(heiro[idx + 1])
			idx += 1
			if idx == len(heiro) - 2:
				idx = -1
			if res[-1] == heiro[heiro.index(s) - 1]:
				return res
	while True:
		heiro.append(heiro[0])
		visited = [0] * n
		f = 0
		for i in heiro:
			visited[i] = 1
		new_heiro = [heiro[0]]
		for i in range(len(heiro) - 1):
			for nv in adj[heiro[i]]:
				if visited[nv] == 1 and nv != heiro[i + 1]:
					new_heiro = graph(nv, heiro[i])
					f = 1
					break
			else:
				new_heiro.append(heiro[len(new_heiro)])
			if f:
				heiro = new_heiro
				break
		else:
			break
	print(len(heiro) - 1)
	for i in heiro[:-1]:
		print(i + 1)
main()


(n, m) = map(int, input().split())
N = 1010
ans = [0] * (N + 1)
g = [[] for _ in range(N)]
for _ in range(m):
	(a, b) = map(int, input().split())
	g[a].append(b)

def minCircle(s):
	f = [0] * N
	d = [0] * N
	q = []
	q.append(s)
	while q:
		p = q.pop()
		for c in g[p]:
			if not d[c]:
				f[c] = p
				d[c] = 1
				q.append(c)
		if d[s]:
			break
	p = f[s]
	ret = []
	ret.append(s)
	while p and p != s:
		ret.append(p)
		p = f[p]
	return ret
for i in range(1, n + 1):
	t = minCircle(i)
	if len(t) > 1 and len(t) < len(ans):
		ans = t
if len(ans) == N + 1:
	print(-1)
else:
	print(len(ans))
	for i in ans:
		print(i)


(n, m) = map(int, input().split())
ans = [0] * (n + 1)
import collections
g = collections.defaultdict(set)
for _ in range(m):
	(a, b) = map(int, input().split())
	g[a - 1].add(b - 1)

def minCircle(s):
	f = [None] * n
	visited = set()
	q = []
	q.append(s)
	while q:
		node = q.pop()
		for nei in g[node]:
			if nei not in visited:
				f[nei] = node
				visited.add(nei)
				q.append(nei)
		if s in visited:
			break
	p = f[s]
	ret = []
	ret.append(s)
	while p is not None and p != s:
		ret.append(p)
		p = f[p]
	return ret
for i in range(n):
	t = minCircle(i)
	if len(t) > 1 and len(t) < len(ans):
		ans = t
if len(ans) == n + 1:
	print(-1)
else:
	print(len(ans))
	for i in ans:
		print(i + 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)
	exit()
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)


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()
		exit()
print(-1)


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)
			exit()
		else:
			search_path(x, temp + [x])
t = 1
for i in range(n):
	if c[i] == 0:
		ans = search_path(i, [i])
print(-1)


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


import sys
input = sys.stdin.buffer.readline

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()))
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:
			(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])
	k = min(A)
	if k == 10 ** 5:
		print(-1)
		return
	s = A.index(k)
	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
	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()


import sys
sys.setrecursionlimit(10 ** 9)
(N, M) = map(int, input().split())
graph = [set() for _ in range(N + 1)]
for _ in range(M):
	(A, B) = map(int, input().split())
	graph[A].add(B)
visited = [False] * (N + 1)

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

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


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


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')
	exit()
print(-1)


from collections import deque
import sys
input = sys.stdin.buffer.readline
(n, m) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
	(a, b) = map(int, input().split())
	graph[a].append(b)
infi = 10 ** 10

def bfs(start):
	res = (infi, -1)
	dist = [-1] * (n + 1)
	par = [-1] * (n + 1)
	que = deque([])
	que.append(start)
	dist[start] = 0
	while que:
		v = que.popleft()
		for u in graph[v]:
			if dist[u] >= 0:
				continue
			dist[u] = dist[v] + 1
			par[u] = v
			que.append(u)
	for i in range(1, n + 1):
		if i == start:
			continue
		if dist[i] == -1:
			continue
		if start in graph[i]:
			if res[0] > dist[i] + 1:
				res = (dist[i] + 1, i)
	if res[0] == infi:
		return (-1, [])
	cycle_num = res[0]
	v = res[1]
	CYCLE = deque([])
	while v > 0:
		CYCLE.appendleft(v)
		v = par[v]
	return (cycle_num, CYCLE)
jisho = {}
ans = (-1, [])
cycle_num = infi
kouho_v = -1
for i in range(1, n + 1):
	(temp_num, temp_cycle) = bfs(i)
	if temp_num == -1:
		continue
	if cycle_num > temp_num:
		cycle_num = min(cycle_num, temp_num)
		kouho_v = i
		jisho[i] = temp_cycle
if kouho_v == -1:
	print(-1)
	return
else:
	ans_num = cycle_num
	ans_list = jisho[kouho_v]
	print(cycle_num)
	print(*ans_list, sep='\n')


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


import sys
from collections import deque
from collections import defaultdict
import copy
(n, m) = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(n + 1)]
radj = [[] for _ in range(n + 1)]
for _ in range(m):
	(a, b) = map(int, sys.stdin.readline().split())
	adj[a].append(b)
	radj[b]

def searchRoute(i):
	global adj
	nexts = deque()
	route = [i]
	visited = set()
	result = []
	for x in adj[i]:
		if x < i:
			continue
		nroute = copy.copy(route)
		nexts.append((x, nroute))
	while len(nexts) > 0:
		error = False
		found = False
		(x, xroute) = nexts.popleft()
		xroute.append(x)
		visited.add(x)
		for y in adj[x]:
			if y < i:
				continue
			if y == i:
				found = True
				break
			if y in visited:
				break
			yroute = copy.copy(xroute)
			nexts.append((y, yroute))
		if found:
			result = xroute
			break
	return result
heiro = []
for i in range(1, n + 1):
	res = searchRoute(i)
	if len(res) > 0:
		heiro = res
		break
if len(heiro) == 0:
	print(-1)
	exit()
while True:
	visited = set()
	bp = [-1, -1]
	rt = defaultdict(int)
	for i in range(len(heiro)):
		visited.add(heiro[i])
		rt[heiro[i]] = i
		for j in adj[heiro[i]]:
			if j in visited and (not (i == len(heiro) - 1 and j == heiro[0])):
				bp = [i, rt[j]]
				break
		if bp[0] != -1:
			break
	if bp[0] == -1:
		print(len(heiro))
		for i in heiro:
			print(i)
		exit()
	heiro = heiro[bp[1]:bp[0] + 1]


from collections import deque
from copy import deepcopy

def detect_cycle(N, repn):
	color = ['WHITE'] * (N + 1)
	unfinished_vertex = set([i for i in range(1, N + 1)])
	cycle = []
	Repn = deepcopy(repn)

	def dfs(u0):
		deq = deque([u0])
		color[u0] = 'GRAY'
		while deq != deque([]) and cycle == []:
			u = deq[-1]
			if len(Repn[u]) != 0:
				v = Repn[u].popleft()
				if color[v] == 'WHITE':
					color[v] = 'GRAY'
					deq.append(v)
				elif color[v] == 'GRAY':
					cycle.append(v)
			else:
				deq.pop()
				color[u] = 'BLACK'
				unfinished_vertex.remove(u)
		return deq
	while cycle == [] and unfinished_vertex != set([]):
		u = unfinished_vertex.pop()
		unfinished_vertex.add(u)
		deq = dfs(u)
	if cycle != []:
		v = cycle.pop()
		while True:
			u = deq.pop()
			cycle.append(u)
			if u == v:
				break
		cycle.reverse()
		return cycle
	else:
		return []

def minimize_cycle(cycle, repn):
	length = len(cycle)
	cycle_idx = {u: i for (i, u) in enumerate(cycle)}
	minimized = False
	for (i, u) in enumerate(cycle):
		if minimized == True:
			break
		else:
			for v in repn[u]:
				if v in cycle_idx.keys():
					j = cycle_idx[v]
					if i + 1 == j:
						continue
					elif i == length - 1 and j == 0:
						continue
					elif i < j:
						reduced_cycle = cycle[:i + 1] + cycle[j:]
						minimized = True
						break
					else:
						reduced_cycle = cycle[j:i + 1]
						minimized = True
						break
	if minimized == True:
		return (reduced_cycle, minimized)
	else:
		return (cycle, minimized)

def main():
	(N, M) = map(int, input().split())
	repn = [deque([]) for i in range(N + 1)]
	for _ in range(M):
		(a, b) = map(int, input().split())
		repn[a].append(b)
	cycle = detect_cycle(N, repn)
	if cycle == []:
		print(-1)
		exit()
	minimized = True
	while minimized == True:
		(cycle, minimized) = minimize_cycle(cycle, repn)
	print(len(cycle))
	for u in cycle:
		print(u)
main()


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

class Graph(object):

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

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

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

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

class Dijkstra(object):

	def __init__(self, graph, start):
		self.g = graph.graph
		self.dist = defaultdict(lambda : INF)
		self.dist[start] = 0
		self.prev = defaultdict(lambda : None)
		self.Q = []
		heappush(self.Q, (self.dist[start], start))
		while self.Q:
			(dist_u, u) = heappop(self.Q)
			if self.dist[u] < dist_u:
				continue
			for (v, cost) in self.g[u]:
				alt = dist_u + cost
				if self.dist[v] > alt:
					self.dist[v] = alt
					self.prev[v] = u
					heappush(self.Q, (alt, v))

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

	def shortest_path(self, goal):
		path = []
		node = goal
		while node is not None:
			path.append(node)
			node = self.prev[node]
		return path[::-1]
(N, M) = map(int, input().split())
g = Graph()
for i in range(M):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g.add_edge(a, b)
	g.add_edge(a, b + N)
	g.add_edge(a + N, b)
ans = INF
j = -1
for i in range(N):
	d = Dijkstra(g, i).dist
	if d[i + N] < ans:
		ans = int(d[i + N])
		j = i
if ans != INF:
	path = Dijkstra(g, j).shortest_path(j + N)[:-1]
	print(ans)
	for node in path:
		print(node + 1)
else:
	print(-1)


(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 math
import os
import sys
sys.setrecursionlimit(1000000)
DEBUG = 'DEBUG' in os.environ

def inp():
	return sys.stdin.readline().rstrip()

def dprint(*value, sep=' ', end='\n'):
	if DEBUG:
		print(*value, sep=sep, end=end)

def solve(N, M, E):
	G = [set() for _ in range(N)]
	for (a, b) in E:
		G[a].add(b)
	visited = set()
	stk = []
	stki = {}

	def dfs(i):
		if i in visited:
			return
		stki[i] = len(stk)
		stk.append(i)
		for j in G[i]:
			if j in visited:
				continue
			if j in stki:
				si = stki[j]
				vset = set(stk[si:])
				loopd = {}
				for k in range(si, len(stk) - 1):
					loopd[stk[k]] = stk[k + 1]
				loopd[stk[-1]] = stk[si]
				return slim_loop(vset, loopd)
			result = dfs(j)
			if result:
				return result
		stk.pop()
		del stki[i]
		visited.add(i)
		return None

	def slim_loop(vset, loopd):
		i = next(iter(vset))
		endi = i
		while True:
			jset = G[i] & vset
			if len(jset) > 1:
				oj = loopd[i]
				for j in jset:
					if j == oj or j not in vset:
						continue
					k = loopd[i]
					while k != j:
						vset.remove(k)
						k = loopd[k]
					loopd[i] = j
				endi = i
			i = loopd[i]
			if i == endi:
				break
		return vset
	for i in range(N):
		if i not in visited:
			result = dfs(i)
			if result:
				return result
	return None

def main():
	(N, M) = [int(e) for e in inp().split()]
	E = []
	for _ in range(M):
		(a, b) = [int(e) - 1 for e in inp().split()]
		E.append((a, b))
	result = solve(N, M, E)
	if not result:
		print('-1')
	else:
		print(len(result))
		for v in result:
			print(v + 1)
main()


def find_cycle(g):
	n = len(g)
	used = [0] * n
	for v in range(n):
		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:
					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:
					v0 = nxt[v]
					while v0 != c:
						is_in_cycle[v0] = 0
						v0 = nxt[v0]
					nxt[v] = c
	i = is_in_cycle.index(1)
	v = nxt[i]
	hist = [i]
	while v != i:
		hist.append(v)
		v = nxt[v]
	return hist
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)


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) = 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
main()


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)


import sys
sys.setrecursionlimit(500000)

def scc(N, G, RG):
	order = []
	used = [0] * N
	group = [None] * N

	def dfs(s):
		used[s] = 1
		for t in G[s]:
			if not used[t]:
				dfs(t)
		order.append(s)

	def rdfs(s, col):
		group[s] = col
		used[s] = 1
		for t in RG[s]:
			if not used[t]:
				rdfs(t, col)
	for i in range(N):
		if not used[i]:
			dfs(i)
	used = [0] * N
	label = 0
	for s in reversed(order):
		if not used[s]:
			rdfs(s, label)
			label += 1
	return (label, group)
from collections import Counter
(N, M) = 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
	groo = grooo[gr]
	path = [v]
	path_set = {v}
	while True:
		aaa = E_set[v] & path_set
		if aaa:
			break
		u = (groo & E_set[v]).pop()
		while E_rev_set[u] - {v} & path_set:
			path_set.remove(path.pop())
		path.append(u)
		path_set.add(u)
		v = u
	for (i, v) in enumerate(path):
		if v in aaa:
			aaa.remove(v)
			if len(aaa) == 0:
				break
	ans = path[i:]
	print(len(ans))
	print('\n'.join(map(str, ans)))
	return
print(-1)


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

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


from collections import defaultdict
import heapq

def main():
	(N, M) = list(map(int, input().split()))
	adj = defaultdict(list)
	for _ in range(M):
		(A, B) = list(map(lambda x: int(x) - 1, input().split()))
		adj[A].append(B)
	min_cycle_size = N + 1
	min_cycle = list()
	for s in range(N):
		parent = [None] * N
		que = [(0, s)]
		while len(que) > 0:
			(dist, node) = heapq.heappop(que)
			if dist > 0 and node == s:
				break
			for next_node in adj[node]:
				if parent[next_node] is not None:
					continue
				parent[next_node] = node
				heapq.heappush(que, (dist + 1, next_node))
		if parent[s] is not None:
			cycle = [s]
			node = parent[s]
			while node != s:
				cycle.append(node)
				node = parent[node]
			if len(cycle) < min_cycle_size:
				min_cycle_size = len(cycle)
				min_cycle = cycle
	if min_cycle_size > N:
		print(-1)
	else:
		print(min_cycle_size)
		for node in min_cycle:
			print(node + 1)
main()


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)
	exit()
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
from io import StringIO
import unittest
import heapq

class TestClass(unittest.TestCase):

	def assertIO(self, input, output):
		(stdout, stdin) = (sys.stdout, sys.stdin)
		(sys.stdout, sys.stdin) = (StringIO(), StringIO(input))
		resolve()
		sys.stdout.seek(0)
		out = sys.stdout.read()[:-1]
		(sys.stdout, sys.stdin) = (stdout, stdin)
		self.assertEqual(out, output)

	def test_入力例_1(self):
		input = '4 5\n1 2\n2 3\n2 4\n4 1\n4 3'
		output = '3\n1\n2\n4'
		self.assertIO(input, output)

	def test_入力例_2(self):
		input = '4 5\n1 2\n2 3\n2 4\n1 4\n4 3'
		output = '-1'
		self.assertIO(input, output)

	def test_入力例_3(self):
		input = '6 9\n1 2\n2 3\n3 4\n4 5\n5 6\n5 1\n5 2\n6 1\n6 2'
		output = '4\n2\n3\n4\n5'
		self.assertIO(input, output)

def resolve():
	(N, M) = (int(i) for i in input().split())
	graph = [[[], []] for i in range(N)]
	for i in range(M):
		(a, b) = (int(i) - 1 for i in input().split())
		graph[a][0].append(b)
		graph[b][1].append(a)
	flg = True
	element = [True for i in range(N)]
	while flg:
		flg = False
		for i in range(N):
			if element[i] == False:
				continue
			if graph[i][0] == []:
				for j in graph[i][1]:
					graph[j][0].remove(i)
				flg = True
				graph[i][1] = []
				element[i] = False
			if graph[i][1] == []:
				for j in graph[i][0]:
					graph[j][1].remove(i)
				flg = True
				graph[i][0] = []
				element[i] = False

	def dicstra(i):
		cost = [100000 for _ in graph]
		cost[i] = 0
		oya = [[] for _ in graph]
		muki = [j[0] for j in graph]
		visited = [False for j in muki]
		q = []
		heapq.heappush(q, [0, i])
		while q:
			(c, ind) = heapq.heappop(q)
			visited[ind] = True
			oya[ind].append(ind)
			for j in muki[ind]:
				if not visited[j] and cost[j] > cost[ind] + 1:
					cost[j] = cost[ind] + 1
					oya[j] = oya[ind][:]
					heapq.heappush(q, [cost[j], j])
		xx = [oya[j] for j in graph[i][1]]
		xx.sort(key=lambda it: len(it))
		for j in xx[0]:
			for k in range(len(graph[j][0])):
				if k >= len(graph[j][0]):
					break
				x = graph[j][0][k]
				if not x in xx[0]:
					graph[j][0].remove(x)
					if k >= len(graph[j][0]):
						break
			for k in range(len(graph[j][1])):
				if k >= len(graph[j][1]):
					break
				x = graph[j][1][k]
				if not x in xx[0]:
					graph[j][1].remove(x)
			if len(graph[j][1]) > 1:
				return j
		else:
			print(len(xx[0]))
			for i in xx[0]:
				print(i + 1)
			return -1
	for i in range(N):
		if element[i]:
			while i >= 0:
				i = dicstra(i)
			break
	else:
		print(-1)
resolve()


from collections import deque

class Graph:

	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
	stack = [root]
	visited = [0 for _ in range(N)]
	visited[root] = 1
	while stack:
		node = stack.pop()
		for adj in g.graph[node]:
			if adj == root:
				break
			if visited[adj]:
				continue
			visited[adj] = 1
			stack.append(adj)
		else:
			continue
		break
	else:
		continue
	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
	if loopsize > dist[root]:
		loopsize = dist[root]
		path = [root]
		node = root
		while prev[node] != root:
			node = prev[node]
			path.append(node)
		res = path
if loopsize != INF:
	print(loopsize)
	for node in res:
		print(node + 1)
else:
	print(-1)


(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
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)
needless = set(range(1, N + 1)) - A_s
for (i, j) in zip(A, B):
	if j not in needless:
		graph[i].append(j)

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():
	(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 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 defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
INF = float('inf')

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

def S():
	return sys.stdin.readline().strip()

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

def find_cycle(graph, vst):
	que = deque([vst])
	dist = [-1] * n
	pre = [-1] * n
	dist[vst] = 0
	flag = False
	while que:
		cur = que.popleft()
		for nxt in graph[cur]:
			if nxt == vst:
				flag = True
				break
			if dist[nxt] != -1:
				continue
			pre[nxt] = cur
			dist[nxt] = dist[cur] + 1
			que += [nxt]
		if flag:
			v = cur
			cycle = []
			while v != -1:
				cycle += [v]
				v = pre[v]
			return cycle
ret_len = INF
(n, m) = LI()
graph = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = LI()
	graph[a - 1] += [b - 1]
min_cycle = 0
for vst in range(n):
	cycle = find_cycle(graph, vst)
	if cycle and len(cycle) < ret_len:
		min_cycle = cycle
		ret_len = len(cycle)
if min_cycle:
	print(ret_len)
	for i in min_cycle:
		print(i + 1)
else:
	print(-1)


from collections import deque
(n, m) = map(int, input().split())
Edge = [list(map(int, input().split())) for i in range(m)]
adj = [[] for _ in range(n)]
for (u, v) in Edge:
	adj[u - 1].append(v - 1)
adj_bit = [0] * n
for i in range(n):
	for j in adj[i]:
		adj_bit[i] += 1 << j
for i in range(n):
	que = deque([(i, 0)])
	visited_a = [0] * n
	while que:
		(v, visited) = que.popleft()
		for dest in adj[v]:
			if visited_a[dest]:
				continue
			if dest == i:
				ans = [i + 1]
				for j in range(1001):
					if visited & 1:
						ans.append(j + 1)
					visited >>= 1
				print(len(ans))
				print(*ans, sep='\n')
				exit()
			if visited & adj_bit[dest]:
				continue
			visited_a[dest] = 1
			que.append((dest, visited + (1 << dest)))
else:
	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:
	cycle = set()
	cycle.add(s)
	pv = prev[s]
	while pv != s:
		cycle.add(pv)
		pv = prev[pv]
	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')


(n, m) = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	edges[a - 1].append(b - 1)
ret = [0] * (n + 1)
for start in range(n):
	parent = [-1] * n
	q = [start]
	while len(q) > 0:
		i = q.pop(0)
		for j in edges[i]:
			if j == start:
				loop = [i]
				while i != start:
					i = parent[i]
					loop.append(i)
				if len(ret) > len(loop):
					ret = loop
				break
			if parent[j] == -1:
				parent[j] = i
				q.append(j)
if len(ret) > n:
	print(-1)
else:
	print(len(ret))
	for i in reversed(ret):
		print(i + 1)


from collections import defaultdict
from collections import deque
import sys
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline
INF = 2 ** 62 - 1

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

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

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

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

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

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

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

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

def slv(N, M, AB):
	g = defaultdict(list)
	for (a, b) in AB:
		g[a].append(b)

	def bfs(s):
		q = deque([s])
		done = {}
		done[s] = 0
		prev = {}
		goal = None
		while q:
			u = q.popleft()
			for v in g[u]:
				if v not in done:
					done[v] = done[u] + 1
					prev[v] = u
					q.append(v)
				if v == s:
					goal = u
					break
		if goal is None:
			return None
		v = goal
		ans = [s]
		while v in prev:
			ans.append(v)
			v = prev[v]
		return ans
	ans = [0] * (2 * N)
	for i in range(1, N + 1):
		a = bfs(i)
		if a and len(ans) > len(a):
			ans = a
	if len(ans) == 2 * N:
		print(-1)
		return
	print(len(ans))
	print(*ans, sep='\n')

def main():
	(N, M) = read_int_n()
	AB = [read_int_n() for _ in range(M)]
	slv(N, M, AB)
main()


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 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)
				if dist[nv] == 0:
					prev[nv] = v
		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)
main()


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

def resolve():
	(n, m) = map(int, input().split())
	E = [[] for _ in range(n)]
	for _ in range(m):
		(a, b) = map(lambda x: int(x) - 1, input().split())
		E[a].append(b)

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


(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)
vis = {}
vs = []

def dfs(i):
	if i in vis:
		if vis[i]:
			del vs[:vs.index(i)]
		return vis[i]
	vis[i] = True
	vs.append(i)
	for j in g[i]:
		if dfs(j):
			return True
	vis[i] = False
	vs.pop()
	return False
for i in range(n):
	if dfs(i):
		break
else:
	print(-1)
	exit()
dist = {v: i for (i, v) in enumerate(vs)}
vis = set()
ws = []
nxt = 0
for i in vs:
	if dist[i] < nxt:
		continue
	k = -1
	for j in g[i]:
		if j not in dist or (dist[j] < dist[i] and j not in vis):
			continue
		if k == -1:
			k = j
			continue
		dj = (dist[j] - dist[i]) % len(vs)
		dk = (dist[k] - dist[i]) % len(vs)
		if dj > dk:
			(k, j) = (j, k)
	nxt = dist[k]
	vis.add(i)
	ws.append(i)
	if k in vis:
		del ws[:ws.index(k)]
		break
print(len(ws))
for i in ws:
	print(i)


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

def BFS(n, E, i0=0):
	Q = deque([a for a in E[i0]])
	D = [INF] * n
	for a in E[i0]:
		D[a] = 1
	while Q:
		x = Q.popleft()
		for c in X[x]:
			if D[c] == INF:
				D[c] = D[x] + 1
				Q.append(c)
	return D
Y = [BFS(N, X, i)[i] for i in range(N)]
mi = min(Y)
if mi == INF:
	print(-1)
else:
	for i in range(N):
		if Y[i] == mi:
			s = i
			break
	Z = [-1] * N
	for i in range(N):
		for j in X[i]:
			if Y[j] == mi:
				Z[i] = j
				break
	for i in range(N):
		s = Z[s]
	print(mi)
	for i in range(mi):
		s = Z[s]
		print(s + 1)


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))
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 = []
	v = start_v
	for i in range(ans_len):
		ans.append(v + 1)
		v = prev_v[v]
	print(ans_len)
	print(*ans, sep='\n')


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):
		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)
					break
			if flag:
				break
		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()


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


import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations, combinations
import fractions
import sys

def input():
	return sys.stdin.readline().strip()
(N, M) = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for i in range(M):
	(A, B) = list(map(int, input().split()))
	A -= 1
	B -= 1
	graph[A].append(B)
for start in range(N):
	parent = [-1] * N
	depth = [0] * N
	que = deque([])
	que.append(start)
	depth[start] = 1
	while len(que) > 0:
		node = que.popleft()
		judge = 0
		if len(graph[node]) > 0:
			for node_next in graph[node]:
				if depth[node_next] == 1:
					judge = 1
				if depth[node_next] == 0:
					depth[node_next] = depth[node] + 1
					que.append(node_next)
					parent[node_next] = node
		if judge == 1:
			last = node
			break
	if judge == 1:
		break
if judge != 1:
	print(-1)
	exit()
node_list = deque([last])
while True:
	loc = parent[node_list[0]]
	if loc == -1:
		break
	else:
		node_list.appendleft(loc)
node_set = set([node_list[0]])
for i in range(1, len(node_list)):
	max_depth = -1
	for edge in graph[node_list[i]]:
		if edge in node_set:
			for j in range(i):
				if edge == node_list[j]:
					max_depth = max(max_depth, j)
	if max_depth >= 0:
		start = max_depth
		end = i
		break
	node_set.add(node_list[i])
print(end + 1 - start)
for node in range(start, end + 1):
	print(node_list[node] + 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)
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)
	exit()
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)


INF = 1001001001
(n, m) = map(int, input().split())

def bfs(sv, to_list):
	dist = [INF for i in range(n)]
	hist = [-1 for i in range(n)]
	q = []
	dist[sv] = 0
	q.append(sv)
	while len(q) > 0:
		v = q[0]
		del q[0]
		for j in to_list[v]:
			if dist[j] != INF:
				continue
			hist[j] = v
			dist[j] = dist[v] + 1
			q.append(j)
	min_cycle = INF
	min_hist = -1
	for i in range(n):
		if i == sv:
			continue
		for j in to[i]:
			if j == sv:
				if min_cycle > dist[i]:
					min_cycle = dist[i]
					min_hist = i
	res = []
	temp_v = min_hist
	if min_cycle < INF:
		while temp_v > -1:
			res.append(temp_v)
			temp_v = hist[temp_v]
	else:
		res = [1 for i in range(n + 1)]
	return res
to = [[] for i in range(m)]
for i in range(m):
	(a, b) = map(int, input().split())
	to[a - 1].append(b - 1)
if len(to) == 0:
	print(-1)
else:
	c = [bfs(i, to) for i in range(n)]
	ans = [1 for i in range(n + 1)]
	for i in range(n):
		if len(ans) > len(c[i]):
			ans = c[i]
	if len(ans) == n + 1:
		print(-1)
	else:
		print(len(ans))
		for v in ans[::-1]:
			print(v + 1)


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

def bfs(g, root, memo, backtrack):
	q = deque()
	memo[root] = 0
	q.append(root)
	while q:
		v = q.popleft()
		for c in g[v]:
			if memo[c] > 0:
				continue
			memo[c] = memo[v] + 1
			backtrack[c] = v
			q.append(c)
(n, m) = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = [int(i) - 1 for i in readline().split()]
	g[a].append(b)
res = 1000000
v0 = -1
b0 = None
for v in range(n):
	memo = [-1] * n
	backtrack = [-1] * n
	bfs(g, v, memo, backtrack)
	if 1 < memo[v] < res:
		v0 = v
		b0 = backtrack
		res = memo[v]
if res == 1000000:
	print(-1)
else:
	i = b0[v0]
	ans = [i + 1]
	while i != v0:
		i = b0[i]
		ans.append(i + 1)
	ans.reverse()
	print(res)
	print(*ans, sep='\n')


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):
	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):
		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 = 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):
		return self.find(x) == self.find(y)

	def get_size(self, x):
		x = self.find(x)
		return self.size[x]

def bfs(n):
	clsd = set()
	opnd = collections.deque()
	root = [None] * N
	d_list = [0] * N
	opnd.append(n)
	while len(opnd) != 0:
		now = opnd.popleft()
		clsd.add(now)
		for e in E[now]:
			if e in clsd:
				if e == n:
					res = [now]
					dist = d_list[now] + 1
					while len(res) != dist:
						res.append(root[res[-1]])
					return [list(reversed(res)), dist]
			else:
				opnd.append(e)
				root[e] = now
				d_list[e] = d_list[root[e]] + 1
	return [[], inf]
(N, M) = list(map(int, input().split()))
E = [[] for n in range(N)]
for m in range(M):
	e = list(map(int, input().split()))
	E[e[0] - 1].append(e[1] - 1)
inf = 10 ** 9

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

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
from collections import deque

def resolve():
	(n, m) = map(int, input().split())
	E = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		E[u].append(v)
	A = [None] * n
	for s in range(n):
		dist = [INF] * n
		dist[s] = 0
		Q = deque([s])
		while Q:
			v = Q.popleft()
			for nv in E[v]:
				if dist[nv] != INF:
					continue
				dist[nv] = dist[v] + 1
				if nv != s:
					Q.append(nv)
			if v == s:
				dist[v] = INF
		A[s] = dist
	(d, v0) = min(((A[v][v], v) for v in range(n)))
	if d == INF:
		print(-1)
		return
	print(d)
	prev = [None] * n
	used = [0] * n
	used[0] = 1
	Q = deque([v0])
	while Q:
		flag = True
		v = Q.popleft()
		for nv in E[v]:
			if nv == v0:
				flag = False
				break
			if used[nv]:
				continue
			used[nv] = 1
			prev[nv] = v
			Q.append(nv)
		if not flag:
			break
	ans = []
	while v != v0:
		ans.append(v)
		v = prev[v]
	ans.append(v0)
	print(*map(lambda x: x + 1, ans[::-1]), sep='\n')
resolve()


import sys
(N, M) = map(int, input().split())
d = [set() for _ in range(N + 1)]

def f(v, h, q):
	if d[v] & q:
		l = []
		for x in h[::-1]:
			l = [x] + l
			if x in d[v]:
				break
		L = []
		while v != x:
			for y in l:
				if v in d[y]:
					L = [v] + L
					v = y
					break
		print('\n'.join((str(x) for x in [len(L) + 1, x] + L[::-1])))
		sys.exit()
	for u in d[v]:
		f(u, h + [u], q | {u})
for _ in range(M):
	(a, b) = map(int, input().split())
	d[a].add(b)
v = 0
exec('v+=1;f(v,[v],{v});' * N)
print(-1)


(N, M) = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
	(A[i], B[i]) = map(int, input().split())
C = [[]] * N
for a in A:
	C[a - 1] = [b - 1 for (i, b) in enumerate(B) if A[i] == a]
search_stack = [[]] * N
visited = [[]] * N
next_position = [-1] * N
for i in range(N):
	search_stack[i] = [i]
	visited[i] = []
	while search_stack[i] != []:
		next_position[i] = search_stack[i].pop(0)
		visited[i].append(next_position[i])
		for node in C[next_position[i]]:
			if node == i:
				visited[i].append(node)
				search_stack[i] = []
				break
			elif node in visited[i]:
				continue
			elif node in search_stack[i]:
				continue
			elif C[node] == []:
				continue
			else:
				search_stack[i].append(node)
short = None
for v in visited:
	if len(v) >= 2 and v[0] == v[-1]:
		if not short or len(v) < len(short):
			short = v
if short:
	del short[-1]
	print(len(short))
	for s in short:
		print(s + 1)
else:
	print(-1)


(n, m) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
outdeg = [0] * (n + 1)
for _ in range(m):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	indeg[b] += 1
	outdeg[a] += 1
is_valid = [indeg[i] * outdeg[i] for i in range(n + 1)]
u = n + 10
ans = []
from collections import deque
for start in range(1, n + 1):
	if not is_valid[start]:
		continue
	q = deque([start])
	visited = [False] * (n + 1)
	prev = [-1] * (n + 1)
	visited[start] = True
	has_ans = False
	while q:
		now = q.popleft()
		for node in graph[now]:
			if node == start:
				prev[node] = now
				has_ans = True
				break
			if visited[node] or not is_valid[node]:
				continue
			prev[node] = now
			visited[node] = True
			q.append(node)
		if has_ans:
			break
	if not has_ans:
		continue
	cnt = 0
	tmp = []
	now = start
	for _ in range(n):
		tmp.append(now)
		cnt += 1
		now = prev[now]
		if now == start or now == -1:
			break
	if cnt < u:
		u = cnt
		ans = tmp
if ans:
	print(u)
	for t in ans:
		print(t)
else:
	print(-1)


import sys, collections as cl, bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10 ** 9 + 7
Max = sys.maxsize

def l():
	return list(map(int, input().split()))

def m():
	return map(int, input().split())

def onem():
	return int(input())

def s(x):
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x) - 1):
		if aa != x[i + 1]:
			a.append([aa, su])
			aa = x[i + 1]
			su = 1
		else:
			su += 1
	a.append([aa, su])
	return a

def jo(x):
	return ' '.join(map(str, x))

def max2(x):
	return max(map(max, x))

def In(x, a):
	k = bs.bisect_left(a, x)
	if k != len(a) and a[k] == x:
		return True
	else:
		return False

def pow_k(x, n):
	ans = 1
	while n:
		if n % 2:
			ans *= x
		x *= x
		n >>= 1
	return ans

def Topo_sort(x, y):
	co = cl.Counter((n for m in x.values() for n in m))
	S = cl.deque([i for i in range(y) if co[i] == 0])
	while S:
		n = S.popleft()
		yield n
		for i in x[n]:
			co[i] -= 1
			if co[i] <= 0:
				S.append(i)
(n, k) = m()
g = cl.defaultdict(set)
gb = cl.defaultdict(set)
for i in range(k):
	(a, b) = m()
	a -= 1
	b -= 1
	g[a].add(b)
	gb[b].add(a)
ans = [None for i in range(n)]
for opt in range(n):
	for start in g[opt]:
		cost = [-1] * n
		cost[start] = 0
		de = [start]
		po = []
		fl = True
		while len(de) > 0 and fl:
			po = []
			for i in de:
				for j in g[i]:
					if cost[j] < 0:
						cost[j] = cost[i] + 1
						po.append(j)
						if j == opt:
							fl = False
			de = po
		if cost[opt] >= 0 and cost[opt] < len(ans):
			p = opt
			ans = [p + 1]
			while p != start:
				for e in gb[p]:
					if cost[p] == cost[e] + 1:
						p = e
						ans.append(p + 1)
						break
if ans[0] == None:
	print(-1)
else:
	print(len(ans))
	for i in ans:
		print(i)


import sys
import io, os
input = sys.stdin.buffer.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)
elif ans:
	print(len(ans))
	print(*ans, sep='\n')
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):
	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)


from collections import deque

def shortest_cycle_path(graph, start):
	n = len(graph)
	dist = [-1] * n
	prev_pos = [-1] * n
	q = deque([start])
	dist[start] = 0
	while q:
		pos = q.pop()
		for next_pos in graph[pos]:
			if dist[next_pos] == -1:
				dist[next_pos] += dist[pos] + 1
				prev_pos[next_pos] = pos
				q.append(next_pos)
	path = []
	path_len = 10 ** 9 + 7
	for goal in range(n):
		if start == goal or dist[goal] == -1:
			continue
		for next_pos in graph[goal]:
			if next_pos == start:
				tmp_path = []
				pos = goal
				while True:
					tmp_path.append(pos)
					if pos == start:
						break
					pos = prev_pos[pos]
				if len(tmp_path) < path_len:
					path_len = len(tmp_path)
					path = [start] + tmp_path[0:]
	path = path[::-1]
	return path
(n, m) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]
for i in range(m):
	(a, b) = info[i]
	a -= 1
	b -= 1
	graph[a].append(b)
len_ans = 10 ** 9 + 7
ans = []
for i in range(n):
	tmp = shortest_cycle_path(graph, i)
	if len(tmp) != 0 and len(tmp) < len_ans:
		len_ans = len(tmp)
		ans = tmp
if ans:
	print(len(ans) - 1)
	for i in range(len(ans) - 1):
		print(ans[i] + 1)
else:
	print(-1)


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

def DD(arg):
	return defaultdict(arg)
INF = float('inf')
(N, M) = list(map(int, input().split()))
graph = {i: [] for i in range(N)}
for _ in range(M):
	(a, b) = list(map(int, input().split()))
	graph[a - 1].append(b - 1)
Q = [i for i in range(N)]
p = [None for i in range(N)]
heiro = []
while Q:
	state = [-1 for i in range(N)]
	Flag = 0
	s = Q.pop()
	if p[s] != None:
		continue
	p[s] = -1
	q = [s]
	while q:
		flag = 0
		x = q.pop()
		if x < 0:
			state[~x] = 0
			continue
		q.append(~x)
		for y in graph[x]:
			state[x] = 1
			if state[y] == -1:
				p[y] = x
				q.append(y)
			elif state[y] == 0:
				continue
			else:
				p[y] = x
				now = x
				while now != y:
					heiro.append(now)
					now = p[now]
				heiro.append(y)
				flag = 1
				break
		if flag:
			Flag = 1
			break
	if Flag:
		break

def graph_size(g):
	ret = 0
	for k in g:
		ret += len(g[k])
	return ret

def squeeze(l):
	global graph
	edges = []
	subgraph = {k: [] for k in l}
	data = DD(lambda : DD(int))
	i = 0
	for k in l:
		for y in graph[k]:
			if y in l:
				subgraph[k].append(y)
				edges.append([0, k, y])
				data[k][y] = i
				i += 1
	graph = subgraph
	s = l[0]
	i = data[p[s]][s]
	edges[i][0] = 1
	now = p[s]
	heiro = [s]
	while now != s:
		heiro.append(now)
		i = data[p[now]][now]
		edges[i][0] = 1
		now = p[now]
	if len(heiro) == len(edges):
		print(len(heiro))
		for x in heiro:
			print(x + 1)
		exit()
	else:
		for (b, k, y) in edges:
			if not b:
				p[y] = k
				now = p[y]
				heiro = [y]
				while now != y:
					heiro.append(now)
					now = p[now]
				squeeze(heiro)
if not heiro:
	print(-1)
else:
	squeeze(heiro)


from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque

def main():
	(node_num, edge_num) = map(int, input().split())
	data = [list(map(int, input().split())) for i in range(edge_num)]
	graph_data = defaultdict(set)
	jisuu_list = [0 for i in range(node_num + 1)]
	for i in range(edge_num):
		(a, b) = data[i]
		graph_data[a].add(b)
		jisuu_list[b] += 1
	now_set = set()
	next_set = set()
	for i in range(1, node_num + 1):
		if jisuu_list[i] == 0:
			now_set.add(i)
	while len(now_set) > 0:
		for now_node in now_set:
			for next_node in graph_data[now_node]:
				jisuu_list[next_node] -= 1
				if jisuu_list[next_node] == 0:
					next_set.add(next_node)
		now_set = next_set
		next_set = set()
	if max(jisuu_list) == 0:
		print(-1)
		sys.exit()
	ans = []
	dist = 10 ** 10
	for i in range(1, node_num + 1):
		if jisuu_list[i] == 0:
			continue
		parent_node = [0 for i in range(node_num + 1)]
		now_set = set()
		next_set = set()
		now_set.add(i)
		dist_kari = 0
		fin_flg = 0
		while len(now_set) > 0:
			dist_kari += 1
			for now_node in now_set:
				for next_node in graph_data[now_node]:
					if next_node == i:
						parent_node[next_node] = now_node
						fin_flg = 1
						break
					if jisuu_list[next_node] == 0:
						continue
					if parent_node[next_node] == 0:
						parent_node[next_node] = now_node
						next_set.add(next_node)
				if fin_flg:
					break
			if fin_flg:
				break
			now_set = next_set
			next_set = set()
		if dist_kari < dist and fin_flg:
			dist = dist_kari
			ans = []
			now_node = parent_node[i]
			ans.append(i)
			while now_node != i:
				ans.append(now_node)
				now_node = parent_node[now_node]
	print(len(ans))
	for ele in ans:
		print(ele)
main()


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

def dfs(v):
	pvs = set([v])
	path = [v]

	def _dfs(v, path):
		for u in d[v]:
			if u in pvs:
				for (i, c) in enumerate(path):
					if c == u:
						break
				return path[i + 1:] + [u]
			if u in vs:
				continue
			pvs.add(u)
			vs.add(u)
			loop = _dfs(u, path + [u])
			pvs.remove(u)
			if loop:
				return loop
		return False
	return _dfs(v, path)

def dfs_w(v):
	pvs = set([])
	nvs = [v]
	path = []
	while True:
		if len(nvs) == 0:
			break
		v = nvs.pop()
		if v < 0:
			pvs.remove(path[-1])
			path.pop()
		else:
			path.append(v)
			pvs.add(v)
			vs.add(v)
			for u in d[v]:
				if u in pvs:
					for (i, c) in enumerate(path):
						if c == u:
							break
					return path[i + 1:] + [u]
				if u in vs:
					continue
				nvs += [-v, u]
	return False
d = [set() for _ in range(N + 1)]
for _ in range(M):
	(a, b) = [int(x) for x in input().strip().split(' ')]
	d[a].add(b)
vs = set()
for i in range(N):
	i += 1
	if i in vs:
		continue
	vs.add(i)
	loop = dfs_w(i)
	if loop:
		break
if not loop:
	print(-1)
	import sys
	sys.exit()
v2i = [-1 for _ in range(N + 1)]
for (i, v) in enumerate(loop):
	v2i[v] = i
(nloop, pvs) = ([], set())
v = loop[0]
f = False
while True:
	nloop.append(v)
	pvs.add(v)
	max_i = max_i_l = -1
	for u in d[v]:
		if v2i[u] == -1:
			continue
		if v2i[v] > v2i[u] and u in pvs:
			f = True
			max_i_l = max(max_i_l, v2i[u])
		if v2i[u] > v2i[v]:
			max_i = max(max_i, v2i[u])
	if f:
		if max_i_l < 0:
			1 / 0
		nloop.append(loop[max_i_l])
		break
	if max_i < 0:
		1 / 0
	v = loop[max_i]
for (i, x) in enumerate(nloop):
	if x == nloop[-1]:
		break
nloop = nloop[i + 1:]
print(len(nloop))
for v in nloop:
	print(v)


import sys
sys.setrecursionlimit(10 ** 7)
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = 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:]
				func(ary)
	print(len(path))
	for v in path:
		print(v + 1)
	exit()

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


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
(n, m) = map(int, input().split())
G = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a].append(b)
from collections import deque
inf = float('inf')
ans = inf
ss = []

def bfs(i):
	global ans, ss
	dist = [inf] * n
	prev = [None] * n
	que = deque()
	for to in G[i]:
		que.append(to)
		dist[to] = 1
		prev[to] = i
	while que:
		cur = que.popleft()
		if cur == i:
			break
		for to in G[cur]:
			if dist[to] != inf:
				continue
			dist[to] = dist[cur] + 1
			prev[to] = cur
			que.append(to)
	if dist[i] < ans:
		ans = dist[i]
		ss = [i]
		for _ in range(ans - 1):
			ss.append(prev[ss[-1]])
for i in range(n):
	bfs(i)
if ans == inf:
	print(-1)
else:
	print(ans)
	for i in reversed(ss):
		print(i + 1)


import sys
sys.setrecursionlimit(10 ** 7)

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

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


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


def dijkstra_back(s, t, n, w, cost):
	import heapq
	prev = [s] * n
	d = [float('inf')] * n
	used = [False] * n
	d[s] = 0
	q = []
	heapq.heapify(q)
	heapq.heappush(q, (0, s))
	while q:
		(c, v) = heapq.heappop(q)
		if d[v] < c:
			continue
		for i in range(len(to[v])):
			k = to[v][i]
			if d[k] > d[v] + cost[v][k]:
				d[k] = d[v] + cost[v][k]
				heapq.heappush(q, (d[k], k))
				prev[k] = v
	path = [t]
	while prev[t] != s:
		path.append(prev[t])
		prev[t] = prev[prev[t]]
	path.append(s)
	path = path[::-1]
	return path
(N, M) = map(int, input().split())
fr = {i: set([]) for i in range(1, N + 1)}
to = {i: set([]) for i in range(1, N + 1)}
for i in range(0, M):
	(a, b) = map(int, input().split())
	fr[b].add(a)
	to[a].add(b)
delete = set([])
flag = 1
while flag == 1:
	flag = 0
	for i in range(1, N + 1):
		if not i in delete and (delete >= fr[i] or delete >= to[i]):
			delete.add(i)
			flag = 1
node = [i for i in range(1, N + 1)]
save = set(node) - delete
if save:
	hen = []
	for i in save:
		fr[i] = fr[i] & save
		to[i] = to[i] & save
		fr[i] = list(fr[i])
		to[i] = list(to[i])
	for i in save:
		for j in fr[i]:
			hen.append((j, i))
	save = list(save)
	cost = [[float('inf') for i in range(0, N + 1)] for i in range(0, N + 1)]
	for i in range(0, len(hen)):
		(a, b) = hen[i]
		cost[a][b] = 1
	ansc = 10 ** 10
	ans = []
	for i in range(len(save)):
		for j in fr[save[i]]:
			test = dijkstra_back(save[i], j, N + 1, len(hen), cost)
			if len(test) < ansc:
				ansc = len(test)
				ans = test
	print(ansc)
	for i in range(0, ansc):
		print(ans[i])
else:
	print(-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:
			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)


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


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

def dfs(index, visited, cycle):
	visited[index] = True
	cycle.append(index)
	for i in edges[index]:
		if visited.get(i):
			return cycle[cycle.index(i):]
		ret = dfs(i, visited, cycle)
		if ret:
			return ret
	visited[index] = False
	cycle.pop(-1)
	return None

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


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


from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

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

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

	def add_edge(self, src, dst, weight=1):
		self.graph[src].append((dst, weight))

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

class Dijkstra(object):

	def __init__(self, graph, start):
		self.g = graph.graph
		self.dist = defaultdict(lambda : float('inf'))
		self.dist[start] = 0
		self.prev = defaultdict(lambda : None)
		self.Q = []
		heappush(self.Q, (self.dist[start], start))
		while self.Q:
			(dist_u, u) = heappop(self.Q)
			if self.dist[u] < dist_u:
				continue
			for (v, weight) in self.g[u]:
				alt = dist_u + weight
				if self.dist[v] > alt:
					self.dist[v] = alt
					self.prev[v] = u
					heappush(self.Q, (alt, v))

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

	def shortest_path(self, goal):
		path = []
		node = goal
		while node is not None:
			path.append(node)
			node = self.prev[node]
		return path[::-1]
g = Graph()
(N, M) = [int(i) for i in input().split()]
for i in range(M):
	(u, v) = [int(i) for i in input().split()]
	g.add_edge(u - 1, v - 1, 1)
	g.add_edge(u - 1, v - 1 + N, 1)
ans_n = 10 ** 6
ans_index = -1
for i in range(N):
	d = Dijkstra(g, i)
	ans_n_ = d.dist[i + N]
	if ans_n_ < ans_n:
		ans_index = i
		ans_n = ans_n_
if ans_n == 10 ** 6:
	print(-1)
else:
	d = Dijkstra(g, ans_index)
	ans = d.shortest_path(ans_index + N)
	ans.sort()
	print(ans_n)
	for j in range(ans_n):
		print(ans[j] + 1)


import sys
from collections import deque
input = sys.stdin.readline
(N, M) = list(map(int, input().split()))
neighbor = [[] for i in range(N)]
for i in range(M):
	(a, b) = list(map(int, input().split()))
	neighbor[a - 1].append(b - 1)
rflag = False
for s in range(N):
	pre = [-1] * N
	start = s
	queue = [start]
	while len(queue) > 0:
		nq = []
		for i in queue:
			for j in neighbor[i]:
				if pre[j] == -1:
					pre[j] = i
					nq.append(j)
					if j == start:
						rflag = True
						break
			if rflag:
				break
		if rflag:
			break
		queue = nq
	if rflag:
		break
if not rflag:
	print(-1)
else:
	v = [0] * N
	v[j] = 1
	roop = [j]
	i = j
	while pre[i] != j:
		pret = pre[i]
		roop.append(pret)
		v[pret] = 1
		i = pret
	roop = roop + [j]
	roop = roop[::-1]
	update = True
	while update:
		update = False
		for (i, vi) in enumerate(roop):
			if i == len(roop) - 1:
				break
			for ni in neighbor[vi]:
				if ni != roop[i + 1] and v[ni] == 1:
					pre[ni] = vi
					v = [0] * N
					v[ni] = 1
					roopn = [ni]
					j = ni
					while pre[j] != ni:
						pret = pre[j]
						roopn.append(pret)
						v[pret] = 1
						j = pret
					roopn = roopn + [ni]
					update = True
					roop = roopn[::-1]
					break
			if update:
				break
	K = len(roop) - 1
	print(K)
	print(*map(lambda x: x + 1, roop[:-1]), sep='\n')


(N, M) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in [0] * M]
E = [{} for _ in [0] * N]
Eb = [{} for _ in [0] * N]
for (a, b) in AB:
	E[a - 1][b - 1] = 1
	Eb[b - 1][a - 1] = 1
import heapq

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


def main():
	import sys
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 7)
	from collections import Counter, deque
	from itertools import combinations, permutations, accumulate, groupby, product
	from bisect import bisect_left, bisect_right
	from heapq import heapify, heappop, heappush
	import math
	(n, m) = map(int, input().split())
	adj = [[] for _ in range(n)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		adj[a - 1].append(b - 1)

	def bfs(start):
		pre = [-1] * n
		d = deque([start])
		res = []
		while d:
			v = d.popleft()
			for nv in adj[v]:
				if nv == start:
					path = []
					while v != -1:
						path.append(v + 1)
						v = pre[v]
					if not res or len(res) > len(path):
						res = path
					break
				if pre[nv] != -1:
					continue
				pre[nv] = v
				d.append(nv)
		return res
	res = [0] * (n + 1)
	for i in range(n):
		temp = bfs(i)
		if temp and len(res) > len(temp):
			res = temp
	if len(res) <= n:
		print(len(res))
		print(*res, sep='\n')
	else:
		print(-1)
main()


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

def bfs(links, start):
	parent = [-1] * (n + 1)
	selfdepth = 10 ** 6
	d = deque()
	done = {start}
	d.append((start, 0))
	while d:
		(edge, depth) = d.popleft()
		for i in links[edge]:
			if i == start:
				selfdepth = depth + 1
				parent[i] = edge
				return (selfdepth, parent)
			if not i in done:
				parent[i] = edge
				d.append((i, depth + 1))
				done.add(i)
	return (selfdepth, parent)
k = 10 ** 6
start = -1
for i in range(1, n + 1):
	(selfdepth, parent_tmp) = bfs(links, i)
	if k > selfdepth:
		k = selfdepth
		start = i
		parent_k = parent_tmp
if start == -1:
	print(-1)
	exit()
print(k)
print(start)
now = parent_k[start]
cnt = 0
while now != start:
	print(now)
	now = parent_k[now]


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


import sys
from collections import deque

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


import heapq

def dijkstra(adj, start):
	prev = [0] * len(adj)
	dist = [float('inf')] * len(adj)
	dist[start] = 0
	q = []
	heapq.heappush(q, [0, start])
	while q:
		(min_dist, v_from) = heapq.heappop(q)
		if min_dist > dist[v_from]:
			continue
		v_tos = adj[v_from]
		for v_to in v_tos:
			if min_dist + v_to[1] < dist[v_to[0]]:
				dist[v_to[0]] = min_dist + v_to[1]
				prev[v_to[0]] = v_from
				heapq.heappush(q, [dist[v_to[0]], v_to[0]])
	return (dist, prev)
(N, M) = map(int, input().split())
adj = [[] for _ in range(2 * N + 1)]
flg = 1
see = [0] * (N + 1)
for _ in range(M):
	(A, B) = map(int, input().split())
	adj[A].append([B, 1])
	adj[A].append([B + N, 1])
ans_best = []
len_ans = N + 1
for start in range(1, N + 1):
	if flg == 0:
		if see[start] == 0:
			continue
	ans = []
	(dist, prev) = dijkstra(adj, start)
	if dist[start + N] < 10 ** 10:
		k = start + N
		while k != start:
			k = prev[k]
			ans.append(k)
		if len(ans) < len_ans:
			ans_best = ans
			len_ans = len(ans)
			if flg:
				for a in ans:
					see[a] = 1
				flg = 0
if len_ans == N + 1:
	print(-1)
else:
	print(len_ans)
	for a in ans_best:
		print(a)


(N, M) = map(int, input().split())
data = [[] for i in range(N + 1)]
for i in range(M):
	(A, B) = map(int, input().split())
	data[A].append(B)
lst = []
for i in range(1, N + 1):
	flag = [0] * (N + 1)
	parent = [0] * (N + 1)
	que = [i]
	while que:
		h = []
		for u in que:
			for v in data[u]:
				if flag[v] == 0:
					flag[v] = 1
					parent[v] = u
					h.append(v)
		que = h
	if parent[i] == 0:
		continue
	lsls = [i]
	zzz = i
	while True:
		zzz = parent[zzz]
		if zzz == i:
			break
		lsls.append(zzz)
	lst.append(lsls)
inf = float('inf')
k = inf
ans = None
for u in lst:
	if k > len(u):
		ans = u
		k = len(u)
if k == inf:
	print(-1)
else:
	print(k)
	for v in ans:
		print(v)


from collections import deque

def resolve():
	(N, M) = map(int, input().split())
	G = [[] for _ in range(N)]
	for _ in range(M):
		(a, b) = map(lambda x: int(x) - 1, 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)
resolve()


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
YesNo = lambda b: bool([print('Yes')] if b else print('No'))
YESNO = lambda b: bool([print('YES')] if b else print('NO'))
int1 = lambda x: int(x) - 1
(N, M) = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int1, input().split())
	edge[a].append(b)
used = [False] * N
for i in range(N):
	if used[i] == True:
		continue
	stack = [i]
	path = []
	while stack:
		v = stack.pop()
		if v >= 0:
			used[v] = True
			path.append(v)
			for nv in edge[v]:
				if not used[nv]:
					stack.append(~v)
					stack.append(nv)
				elif nv in path:
					path.append(nv)
					break
			else:
				continue
			break
		else:
			path.pop()
	else:
		continue
	break
else:
	print(-1)
	exit()
cycle = path[path.index(path[-1]):]
while True:
	s = set(cycle)
	next_cycle = []
	for (i, v) in enumerate(cycle[:-1]):
		next_cycle.append(v)
		for nv in edge[v]:
			if nv == cycle[i + 1]:
				continue
			if nv in s:
				next_cycle.extend(cycle[cycle.index(nv):])
				break
		else:
			continue
		break
	else:
		break
	cycle = []
	ss = set()
	for v in next_cycle:
		if v in ss:
			vv = v
			break
		ss.add(v)
	f = False
	for v in next_cycle:
		if v == vv:
			cycle.append(v)
			if not f:
				f = True
			else:
				break
		elif f:
			cycle.append(v)
print(len(cycle) - 1)
for v in cycle[:-1]:
	print(v + 1)


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

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

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

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

def D():

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

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

def F():

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

	def dijkstra(s):
		dist = defaultdict(lambda : float('inf'))
		dist[s, 0] = 0
		q = [(0, s, 0)]
		pre = [None] * n
		while q:
			(dx, x, k) = heappop(q)
			if dx < dist[x, k]:
				continue
			if x == s and k:
				break
			for y in v[x]:
				if d[y] != 2:
					continue
				if y == s:
					nk = 1
				else:
					nk = 0
				nd = dx + 1
				if nd < dist[y, nk]:
					dist[y, nk] = nd
					pre[y] = x
					heappush(q, (nd, y, nk))
		return (dist, pre)
	(n, m) = LI()
	v = [[] for i in range(n)]
	for i in range(m):
		(a, b) = LI()
		a -= 1
		b -= 1
		v[a].append(b)
	d = [0] * n
	pre = [None] * n
	now = [False] * n
	k = []
	for x in range(n):
		if not d[x]:
			d[x] = 1
			now[x] = True
			dfs(x, d)
			if k:
				break
			now[x] = False
	else:
		print(-1)
		return
	(di, p, s) = (float('inf'), [], None)
	for x in range(n):
		if d[x] != 2:
			continue
		(dist, pre) = dijkstra(x)
		if dist[x, 1] < di:
			di = dist[x, 1]
			p = pre
			s = x
	ans = [s + 1]
	x = p[s]
	while x != s:
		ans.append(x + 1)
		x = p[x]
	ans.sort()
	print(len(ans))
	for i in ans:
		print(i)
	return
F()


def f_pure():
	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):
		dist = [-1] * N
		previous = [-1] * 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
			for next_node in graph[t]:
				if next_node == s:
					ans_tmp = [s]
					current_node = t
					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())


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


from collections import deque

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

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


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(n, m) = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
	(a, b) = map(int, input().split())
	ns[a - 1].add(b - 1)
seen = [False] * n
done = [False] * n
hist = []

def dfs(u, pos):
	seen[u] = True
	hist.append(u)
	for v in ns[u]:
		if done[v]:
			continue
		elif seen[v]:
			pos = v
			return pos
		else:
			pos = dfs(v, pos)
			if pos >= 0:
				return pos
	done[u] = True
	hist.pop()
	return pos

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


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]
			if not (not s or s == {start}):
				continue
			for dest in edges[v]:
				if dest == start:
					print(len(route))
					print(*route, sep='\n')
					return
				if visited[dest]:
					continue
				visited[dest] = 1
				dq.append((dest, route | {dest}))
	print(-1)

def __starting_point():
	solve()
__starting_point()


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
L = 10 ** 14
num = -1
for n in range(N):
	q = [n]
	checked = [False] * N
	checked[n] = True
	before = [None] * N
	c = 0
	ok = False
	while q:
		c += 1
		qq = []
		for p in q:
			for np in graph[p]:
				if not checked[np]:
					before[np] = p
					qq.append(np)
					checked[np] = True
				elif np == n:
					before[np] = p
					ok = True
					break
		if ok:
			break
		q = qq
	if ok and c < L:
		L = c
		num = n
		ans = []
		k = n
		for _ in range(c):
			k = before[k]
			ans.append(k + 1)
if num == -1:
	print(-1)
else:
	print(len(ans))
	for a in reversed(ans):
		print(a)


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 sys
from collections import deque

def main():
	(N, M) = map(int, input().split())
	E = [set() for _ in range(N)]
	for _ in range(M):
		(a, b) = map(int, input().split())
		E[a - 1].add(b - 1)
	for start in range(N):
		visited = [0] * N
		Q = deque([(start, {start})])
		(append, popleft) = (Q.append, Q.popleft)
		visited[start] = 1
		while Q:
			(v, route) = popleft()
			s = route & E[v]
			if s and s != {start}:
				continue
			for dest in E[v]:
				if dest == start:
					print(len(route))
					print(*[n + 1 for n in route], sep='\n')
					return
				if visited[dest]:
					continue
				visited[dest] = 1
				append((dest, route | {dest}))
	print(-1)
	return
main()


import math
import sys
from collections import deque, defaultdict
(N, M) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
g = [set() for _ in range(N)]
for (a, b) in AB:
	g[a - 1].add(b - 1)

def find_loop(s, subnode):
	q = deque([(s, {s})])
	visited = defaultdict(lambda : math.inf)
	while len(q) > 0:
		(node, p) = q.popleft()
		for to_node in g[node] & subnode:
			if to_node == s:
				return p
			if visited[to_node] > len(p):
				visited[to_node] = len(p)
				q.append((to_node, p | {to_node}))
	return -1
V = set(range(N))
for i in range(N):
	subnode = find_loop(i, V)
	if subnode != -1:
		break
if subnode == -1:
	print(-1)
	sys.exit()
while True:
	flg = True
	for i in subnode:
		if len(g[i] & subnode) != 1:
			flg = False
			s = i
			break
	if flg:
		break
	subnode = find_loop(s, subnode)
print(len(subnode))
for node in subnode:
	print(node + 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)


import sys
sys.setrecursionlimit(10 ** 6)
LI = lambda : list(map(int, input().split()))
(N, M) = LI()
AB = [LI() for _ in range(M)]
link = [[] for _ in range(N)]
for (a, b) in AB:
	link[a - 1].append(b - 1)
impossible = [False] * N

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

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

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

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 deque
(N, M) = map(int, input().split())
v = [[] for _ in range(N)]
for _ in range(M):
	(A, B) = map(int, input().split())
	v[A - 1].append(B - 1)

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


import sys
input = sys.stdin.buffer.readline

def find_cycle(adj, start=0):
	global arrived, finished
	stack = [~start, start]
	history = []
	while stack:
		v = stack.pop()
		if v >= 0:
			arrived[v] = True
			history.append(v)
			for nv in adj[v]:
				if not arrived[nv]:
					stack.append(~nv)
					stack.append(nv)
				elif not finished[nv]:
					index = history.index(nv)
					return history[index:]
		else:
			finished[~v] = True
			history.pop()
	return []
(N, M) = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
	(A, B) = map(int, input().split())
	adj[A - 1].append(B - 1)
arrived = [False] * N
finished = [False] * N
while False in arrived:
	start = arrived.index(False)
	cycle = find_cycle(adj, start)
	if cycle:
		break
if not cycle:
	print(-1)
	exit()
else:
	cycle_updated = True
	while cycle_updated:
		cycle_updated = False
		cycle_index = {v: i for (i, v) in enumerate(cycle)}
		l = len(cycle)
		for (i, v) in enumerate(cycle):
			cv = cycle[i + 1 - l]
			for nv in adj[v]:
				if nv != cv and nv in cycle_index:
					cycle_updated = True
					j = cycle_index[nv]
					if i < j:
						cycle = cycle[:i + 1] + cycle[j:]
					else:
						cycle = cycle[j:i + 1]
					break
			if cycle_updated:
				break
	print(len(cycle))
	print(*[elem + 1 for elem in cycle], sep='\n')


(n, m) = map(int, input().split())
g = [[] for _ in range(1005)]
for i in range(m):
	(a, b) = map(int, input().split())
	g[a].append(b)
vis = [0] * 1005

def dfs(x, p):
	if vis[x]:
		return []
	p.append(x)
	vis[x] = 1
	for v in g[x]:
		if v in p:
			return p
		t = dfs(v, p)
		if len(t):
			return t
	p.pop()
	return []
t = []
for i in range(1, 1 + n):
	t = dfs(i, [])
	if len(t):
		print(0)
		exit(0)
print(-1)


import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7
INF = float('inf')

def getlist():
	return list(map(int, input().split()))

class Graph(object):

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

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

	def add_edge(self, a, b):
		self.graph[a].append(b)

def BFS(G, N, s, g, ans):
	Q = deque()
	Q.append(s)
	dist = [INF] * N
	dist[s] = 0
	prev = [None] * N
	jud = 'No'
	while Q:
		v = Q.popleft()
		for i in G.graph[v]:
			if dist[i] == INF:
				dist[i] = dist[v] + 1
				prev[i] = v
				Q.append(i)
				if i == g:
					jud = 'Yes'
					break
		if jud == 'Yes':
			break
	if ans > dist[g]:
		state = g
		path = [g]
		while True:
			state = prev[state]
			path.append(state)
			if state == s:
				break
		return (dist[g], path[::-1])
	else:
		return (INF, [])

def main():
	(N, M) = getlist()
	G = Graph()
	edgefrom = []
	edgeto = []
	for i in range(M):
		(a, b) = getlist()
		a -= 1
		b -= 1
		edgefrom.append(a)
		edgeto.append(b)
		G.add_edge(a, b)
	ans = 100000
	path = None
	for i in range(M):
		(predis, prepath) = BFS(G, N, edgeto[i], edgefrom[i], ans)
		if predis != INF:
			ans = predis
			path = prepath
	if ans == 100000:
		print(-1)
	else:
		print(ans + 1)
		for i in path:
			print(i + 1)
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
inpl = lambda : list(map(int, input().split()))
(N, M) = inpl()
uv = [set() for _ in range(N)]
vu = [set() for _ in range(N)]
for _ in range(M):
	(A, B) = inpl()
	uv[A - 1].add(B - 1)
	vu[B - 1].add(A - 1)
(EMPTY, LOOP, TREE) = (0, 1, 2)
(ENTER, EXIT) = (0, 1)
status = [EMPTY] * N
for s in range(N):
	states_pool = [(s, [], ENTER)]
	while states_pool:
		(u, chain, flag) = states_pool.pop()
		if flag == EXIT or status[u] == TREE:
			status[u] = TREE
			continue
		elif status[u] == LOOP:
			break
		else:
			status[u] = LOOP
			states_pool.append((u, chain, EXIT))
			new_chain = chain.copy()
			new_chain.append(u)
			for c in uv[u]:
				states_pool.append((c, new_chain, ENTER))
	else:
		continue
	break
else:
	print(-1)
	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
		elif (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)


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

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


import sys
from collections import defaultdict as dd
input = sys.stdin.readline
(N, M) = map(int, input().split())
e = dd(list)
reve = dd(list)
for _ in range(M):
	(u, v) = map(int, input().split())
	e[u].append(v)
	reve[v].append(u)
vis = set()
inc = [0] * (N + 1)

def dfs(x, l):
	global vis
	global inc
	vis.add(x)
	ok = 0
	for y in reve[x]:
		if y in vis:
			inc[x] += 1
	if inc[x] > 1:
		inc[x] = 0
		vis.discard(x)
		return
	for y in e[x]:
		if y == l:
			ok = 1
			continue
		if y in vis:
			inc[x] = 0
			vis.discard(x)
			return
	if ok:
		print(len(vis))
		for v in vis:
			print(v)
		exit(0)
	for y in e[x]:
		dfs(y, l)
	vis.discard(x)
for s in range(1, N + 1):
	dfs(s, s)
print(-1)


from collections import deque
import sys
(N, M) = map(int, input().split())
AB = []
lis = [[] for i in range(N)]
for i in range(M):
	(A, B) = map(int, input().split())
	A -= 1
	B -= 1
	lis[A].append(B)
q = deque([])
first = [-1] * (N + 1)
first[0] = 0
first[-1] = 0
q.append(first)
end = [True] * N
end[0] = False
while len(q) > 0:
	now = q.pop()
	lasp = now[-1]
	nownum = now[lasp]
	for nex in lis[lasp]:
		if now[nex] == -1:
			ncopy = now.copy()
			ncopy[nex] = nownum + 1
			ncopy[-1] = nex
			end[nex] = False
			q.append(ncopy)
		else:
			flag = True
			for i in range(N):
				if now[i] >= 0:
					for j in lis[i]:
						if (now[j] >= now[nex] and now[j] != now[i] + 1) and (not (i == lasp and j == nex)):
							flag = False
							break
				if not flag:
					break
			if flag:
				ans = []
				for i in range(N):
					if now[i] >= now[nex]:
						ans.append(i + 1)
				print(len(ans))
				for i in ans:
					print(i)
				sys.exit()
	if len(q) == 0:
		for i in range(N):
			if end[i]:
				first = [-1] * (N + 1)
				first[i] = 0
				first[-1] = i
				q.append(first)
				end[i] = False
				break
print(-1)


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


def examA():

	class Dijkstra(object):

		def __init__(self, edges, start=0):
			self.__dist = [inf] * len(edges)
			self.__dist[start] = 0
			self.__calculate(edges, start)

		@property
		def dist(self):
			return self.__dist

		def __calculate(self, edges, start):
			Q = [(0, start)]
			while Q:
				(dist, v) = heapq.heappop(Q)
				if self.dist[v] < dist:
					continue
				for (u, cost) in edges[v]:
					if self.dist[u] > self.dist[v] + cost:
						self.__dist[u] = self.dist[v] + cost
						heapq.heappush(Q, (self.dist[u], u))
	(N, L) = LI()
	(V, D) = LI()
	X = [LI() for _ in range(N)]
	X.append([0, V, D])
	X.append([L, 0, 0])
	X.sort()
	V = [[] for _ in range(N + 2)]
	for i in range(N + 1):
		(x1, v1, d1) = X[i]
		r = x1 + d1
		for j in range(i + 1, N + 2):
			(x2, v2, d2) = X[j]
			if r < x2:
				break
			cost = (x2 - x1) / v1
			V[i].append((j, cost))
	dij = Dijkstra(V, 0)
	ans = dij.dist[-1]
	if ans >= inf:
		print('impossible')
		return
	print('{:.18f}'.format(ans))
	return

def examB():
	(N, K) = LI()
	H = 11
	W = 7
	S = [[0] * (W + 1) for _ in range(H + 3)]
	for h in range(H + 2):
		for w in range(W):
			S[h + 1][w + 1] = S[h][w + 1] + S[h + 1][w] - S[h][w] + (7 * h + w + 1)
	base = 0
	for h in range(H):
		for w in range(W - 2):
			cur = S[h + 3][w + 3] - S[h + 3][w] - S[h][w + 3] + S[h][w]
			if cur % 11 == K:
				base += 1
	ans = base * ((N - 2) // 11)
	rest = (N - 2) % 11
	for h in range(rest):
		for w in range(W - 2):
			cur = S[h + 3][w + 3] - S[h + 3][w] - S[h][w + 3] + S[h][w]
			if cur % 11 == K:
				ans += 1
	print(ans)
	return

def examC():
	(N, K) = LI()
	A = LI()
	loop = 2 ** N
	ans = inf
	for i in range(loop):
		cnt = 0
		need = 0
		highest = 0
		for j in range(N):
			if i & 1 << j == 0:
				if highest < A[j]:
					need = inf
					break
				continue
			cnt += 1
			if highest >= A[j]:
				need += highest + 1 - A[j]
				highest = highest + 1
			else:
				highest = A[j]
		if cnt >= K and need < ans:
			ans = need
	print(ans)
	return

def examD():

	def cycle(neighbor, start, ring_size, node):
		visited = [False] * node
		stack = []
		stack.append([start])
		visited[start] = True
		while stack:
			curr_path = stack.pop()
			if len(curr_path) > ring_size:
				continue
			last = curr_path[-1]
			for nei in neighbor[last]:
				if nei in curr_path:
					if len(curr_path) == 0:
						continue
					if len(curr_path) <= ring_size and curr_path[0] == nei:
						new_path = copy(curr_path)
						return new_path
					elif len(curr_path) <= ring_size:
						return cycle(neighbor, nei, ring_size - 1, node)
				if visited[nei]:
					continue
				visited[nei] = True
				new_path = copy(curr_path)
				new_path.append(nei)
				stack.append(new_path)
		return -1
	(N, M) = LI()
	V = [[] for _ in range(N)]
	for _ in range(M):
		(a, b) = LI()
		a -= 1
		b -= 1
		V[a].append(b)
	loop = -1
	for i in range(N):
		loop = cycle(V, i, N, N)
		if loop != -1:
			break
	if loop == -1:
		print(-1)
		return
	while True:
		next = -1
		for k in loop:
			next = cycle(V, k, len(loop) - 1, N)
			if next != -1:
				break
		if next == -1:
			break
		loop = next
	ans = loop
	print(len(ans))
	for v in ans:
		print(v + 1)
	return
import sys, bisect, itertools, heapq, math, random
from copy import copy, deepcopy
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = 10 ** (-12)
alphabet = [chr(ord('a') + i) for i in range(26)]
sys.setrecursionlimit(10 ** 6)
examD()


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


import sys
from collections import deque

def shave(fwd_link, bwd_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)
	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) = 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) = map(int, line.split())
	a -= 1
	b -= 1
	fwd_link[a].add(b)
	bwd_link[b].add(a)
solve(fwd_link, bwd_link)


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
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)
	exit()
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]))
		exit()
	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()))
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
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 = [list(map(int, input().split())) for _ in range(m)]
from collections import defaultdict, deque
g = defaultdict(list)
for (a, b) in ab:
	g[a - 1].append(b - 1)
ans = None
for start in range(n):
	visited = [0] * n
	visited[start] = 1
	q = deque([start])
	prev = [None] * n
	f = False
	while q:
		cur = q.popleft()
		for target in g[cur]:
			if visited[target] == 0:
				visited[target] = 1
				q.append(target)
				prev[target] = cur
			if target == start:
				f = True
				break
		if f:
			break
	if f:
		loop = [target]
		while cur != None:
			loop.append(cur)
			cur = prev[cur]
		loop = loop[::-1]
		v = set(loop)
		f2 = True
		for i in range(len(loop) - 1):
			(a, b) = (loop[i], loop[i + 1])
			for target in g[a]:
				if target in v and target != b:
					f2 = False
					break
			if f2 == False:
				break
		if f2:
			ans = loop[:-1]
			break
if ans == None:
	print(-1)
else:
	print(len(ans))
	for _ans in ans:
		print(_ans + 1)


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

def solve():
	(N, M) = map(int, input().split())
	d = {i: [] for i in range(1, N + 1)}
	l = []
	INF = 10 ** 12
	v = INF
	for _ in range(M):
		(A, B) = map(int, input().split())
		d[A].append(B)
		l.append((A, B))
	ans = []
	for (i, j) in l:
		INF = 10 ** 12
		dist = [-1] * (N + 1)
		prev = [-1] * (N + 1)
		dist[j] = 0
		prev[j] = 0
		q = deque([j])
		while q:
			a = q.popleft()
			for b in d[a]:
				if dist[b] == -1:
					dist[b] = dist[a] + 1
					prev[b] = a
					q.append(b)
		if v > dist[i] + 1 and dist[i] != -1:
			v = dist[i] + 1
			buf = i
			ans = []
			while buf:
				ans.append(buf)
				buf = prev[buf]
	if ans:
		print(len(ans))
		for i in ans:
			print(i)
	else:
		print(-1)
solve()


import sys
sys.setrecursionlimit(10 ** 9)
(N, M) = map(int, input().split())
adjL = [set() for _ in range(N)]
for _ in range(M):
	(A, B) = 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)
	sys.exit()
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(map(lambda x: str(x + 1), 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]


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

def dfs(v, l):
	for u in d[v]:
		if u in pvs:
			return l + [u]
		if u in vs:
			continue
		pvs.add(u)
		vs.add(u)
		ll = dfs(u, l + [u])
		pvs.remove(u)
		if ll:
			return ll
	return False
d = [set() for _ in range(N)]
for _ in range(M):
	(a, b) = [int(x) for x in input().strip().split(' ')]
	d[a - 1].add(b - 1)
vs = set()
for i in range(N):
	if i in vs:
		continue
	vs.add(i)
	pvs = set([i])
	loop = dfs(i, [i])
	if loop:
		break
import sys
if not loop:
	print('-1')
	sys.exit()
else:
	ll = []
	lx = loop[-1]
	f = False
	for x in loop:
		if lx == x and (not f):
			f = True
			continue
		if not f:
			continue
		ll.append(x)
	loop = ll
v2i = [-1 for _ in range(N)]
for (i, v) in enumerate(loop):
	v2i[v] = i
i = 0
vs = set()
ss = set()
lnum = len(loop)
ll = []
while True:
	v = loop[i]
	if i in vs:
		f = False
		loop = []
		for x in ll:
			if v == x:
				f = True
			if f:
				loop.append(x)
		break
	m = 0
	for u in d[v]:
		if v2i[u] == -1:
			continue
		if v2i[u] in ss:
			continue
		if v2i[v] > v2i[u]:
			m = max(lnum - v2i[v] + v2i[u], m)
		else:
			m = max(v2i[u] - v2i[v], m)
	for j in range(m - 1):
		ss.add((i + j + 1) % lnum)
	vs.add(i)
	ll.append(v)
	i = (i + m) % lnum
print(len(loop))
for i in loop:
	print(i + 1)


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


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

def best_cycle(a, b):
	(a, b) = itm
	a -= 1
	b -= 1
	Q = deque()
	Q.append([b, [b]])
	visited = [-1] * n
	visited[b] = 1
	while Q:
		(now, path) = Q.popleft()
		for nxt in link[now]:
			if nxt == a:
				return (True, path + [nxt])
			if visited[nxt] != -1:
				continue
			visited[nxt] = 1
			Q.append([nxt, path + [nxt]])
	return (False, [])
mn = 10 ** 10
ans = []
found = False
for itm in ab:
	(a, b) = itm
	(ret, path) = best_cycle(a, b)
	if ret and len(path) < mn:
		ans = path
		mn = len(path)
		found = True
if found:
	print(len(ans))
	for a in ans:
		print(a + 1)
else:
	print(-1)


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

def dfs(v, path):
	lp = 0
	l = N + 1
	for u in d[v]:
		if u in pvs:
			for (i, c) in enumerate(path):
				if c == u:
					break
			nlp = path[i + 1:] + [u]
			nl = len(nlp)
			if nl < l:
				(lp, l) = (nlp, nl)
		if u in vs:
			continue
		pvs.add(u)
		vs.add(u)
		(nl, nlp) = dfs(u, path + [u])
		if nl < l:
			(lp, l) = (nlp, nl)
		pvs.remove(u)
	return (l, lp)
d = [set() for _ in range(N + 1)]
for _ in range(M):
	(a, b) = map(int, input().split(' '))
	d[a].add(b)
for i in range(N):
	v = i + 1
	pvs = set([v])
	(l, lp) = dfs(i + 1, [v])
	if l != N + 1:
		print(l)
		for l in lp:
			print(l)
		break
else:
	print(-1)


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

def bfs(node):
	parents = [None for i in range(N)]
	stack = [node]
	while stack:
		item = stack.pop(0)
		orig = item
		for neighbour in neighbours[item]:
			if visited[neighbour]:
				if parents[neighbour] == None:
					parents[neighbour] = item
				try:
					graph = {neighbour}
					while item != neighbour:
						graph.add(item)
						item = parents[item]
						if item == orig and item != neighbour:
							1 / 0
					print(len(graph))
					for item in graph:
						print(item + 1)
					return True
				except:
					pass
			if not visited[neighbour]:
				parents[neighbour] = item
				visited[neighbour] = True
				stack.append(neighbour)
for i in range(N):
	if not visited[i]:
		if bfs(i):
			break
else:
	print(-1)


import sys
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()
(n, m) = na()
g = [[False] * n for _ in range(n)]
gs = [[] for _ in range(n)]
for i in range(m):
	(s, t) = na()
	gs[s - 1].append(t - 1)
	g[s - 1][t - 1] = True
ans = 999999
best = None
for i in range(n):
	ds = [9999999] * n
	prevs = [-1] * n
	ds[i] = 0
	q = [i]
	qp = 0
	while qp < len(q):
		cur = q[qp]
		qp += 1
		for e in gs[cur]:
			if ds[e] > ds[cur] + 1:
				ds[e] = ds[cur] + 1
				prevs[e] = cur
				q.append(e)
	for j in range(n):
		if g[j][i]:
			if ds[j] + 1 < ans:
				ans = ds[j] + 1
				best = [0] * (ds[j] + 1)
				best[0] = i
				cur = j
				r = -1
				while cur != i:
					best[r] = cur
					r -= 1
					cur = prevs[cur]
if not best:
	print(-1)
else:
	print(ans)
	for x in best:
		print(x + 1)


from collections import deque
(n, m) = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
inverse = [[] for _ in range(n)]
ab = []
for i in range(m):
	(a, b) = [int(item) - 1 for item in input().split()]
	ab.append((a, b))
	edge[a].append(b)
seen = [0] * n
checked = [0] * n
hist = deque()
ret = -1

def dfs(v):
	global ret
	seen[v] = 1
	hist.append(v)
	for nv in edge[v]:
		if checked[nv]:
			continue
		if seen[nv] and (not checked[nv]):
			ret = nv
			return
		dfs(nv)
		if ret != -1:
			return
	hist.pop()
	checked[v] = 1
for i in range(n):
	dfs(i)
	if ret != -1:
		break
if ret == -1:
	print(-1)
	exit()
cycle = []
while hist:
	t = hist.pop()
	cycle.append(t)
	if t == ret:
		break
cycle.reverse()
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]))
		exit()
	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[:]


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


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)
order = defaultdict(int)
x = V.pop()
V.add(x)
q = [x]
order[x] = 1
path = [x]
flag = False
while True:
	y = graph[x][0]
	if order[y] != 0:
		path = path[order[y] - 1:]
		break
	path.append(y)
	order[y] = order[x] + 1
	x = y
V = set(path)
next_v = {u: v for (u, v) in zip(path, path[1:])}
next_v[path[-1]] = path[0]
for (a, b) in AB:
	if not (a in V and b in V):
		continue
	x = next_v[a]
	while x != b:
		V.remove(x)
		x = next_v[x]
	next_v[a] = b
print(len(V))
print(*V, sep='\n')


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

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


from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
sqrt = math.sqrt

def LI():
	return list(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def LI_():
	return [int(i) - 1 for i in input().split()]

def II():
	return int(input())

def IF():
	return float(input())

def LS():
	return list(map(list, input().split()))

def S():
	return list(input().rstrip())

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

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

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

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

def primes(n):
	(n, correction) = (n - n % 6 + 6, 2 - (n % 6 > 1))
	sieve = [True] * (n // 3)
	for i in range(1, int(n ** 0.5) // 3 + 1):
		if sieve[i]:
			k = 3 * i + 1 | 1
			sieve[k * k // 3::2 * k] = [False] * ((n // 6 - k * k // 6 - 1) // k + 1)
			sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = [False] * ((n // 6 - k * (k - 2 * (i & 1) + 4) // 6 - 1) // k + 1)
	return [2, 3] + [3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]]

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

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

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

	def dijkstra(start):
		dist = [inf] * n
		dist[start] = 0
		q = [(0, start)]
		while q:
			(du, u) = heappop(q)
			for i in edg[u]:
				if du + 1 < dist[i]:
					dist[i] = du + 1
					heappush(q, (du + 1, i))
		return dist
	d = [None] * n
	for i in range(n):
		d[i] = dijkstra(i)
	tmp = inf
	tt = None
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			if tmp > d[i][j] + d[j][i]:
				tt = (i, j)
				tmp = d[i][j] + d[j][i]
	if tmp != inf:
		print(tmp)
		(s, g) = tt
		ans1 = [s]
		ans2 = [g]
		q = deque([s])
		while q:
			a = q.pop()
			for ai in redg[a]:
				if g != ai and d[g][ai] + 1 == d[g][a]:
					ans1.append(ai)
					q.append(ai)
					break
		q = deque([g])
		while q:
			a = q.pop()
			for ai in redg[a]:
				if s != ai and d[s][ai] + 1 == d[s][a]:
					ans2.append(ai)
					q.append(ai)
					break
		ans = ans1 + ans2
		for a in ans:
			print(a + 1)
	else:
		print(-1)
	return
F()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
from collections import defaultdict
(n, m) = map(int, input().split())
ns = defaultdict(set)
es = set()
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	ns[u].add(v)
	es.add((u, v))
seen = [False] * n
done = [False] * n
hist = []

def dfs(u, pos):
	seen[u] = True
	hist.append(u)
	for v in ns[u]:
		if done[v]:
			continue
		elif seen[v]:
			pos = v
			return pos
		else:
			pos = dfs(v, pos)
			if pos >= 0:
				return pos
	done[u] = True
	hist.pop()
	return pos

def cycle(hist, pos):
	for (i, u) in enumerate(hist):
		if u == pos:
			break
	return hist[i:]

def sub(hist):
	s = set(hist)
	ss = set(((hist[i], hist[i + 1]) for i in range(len(hist) - 1)))
	ss.add((hist[len(hist) - 1], hist[0]))
	l = None
	for (u, v) in es:
		if u in s and v in s and ((u, v) not in ss):
			l = []
			for (i, k) in enumerate(hist):
				if k == v:
					break
			for j in range(i, len(hist)):
				l.append(hist[j])
				if hist[j] == u:
					break
			else:
				for j in range(len(hist)):
					l.append(hist[j])
					if hist[j] == u:
						break
	if l is None or len(l) == len(hist):
		return hist
	else:
		return sub(l)
ans = None
for u in range(n):
	pos = dfs(u, -1)
	if pos >= 0:
		hist = cycle(hist, pos)
		ans = sub(hist)
		break
if ans is None:
	print(-1)
else:
	print(len(ans))
	write('\n'.join(map(lambda x: str(x + 1), ans)))


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

def find_loop(index, visited, cycle):
	visited[index] = True
	cycle.append(index)
	for i in edges[index]:
		if visited.get(i):
			return cycle[cycle.index(i):]
		ret = find_loop(i, visited, cycle)
		if ret:
			return ret
	visited[index] = False
	cycle.pop(-1)
	return None

def find_local_minimum(cycle):
	nxt = {i: j for (i, j) in zip(cycle, cycle[1:] + cycle[:1])}
	processed = set()
	i = cycle[0]
	while i not in processed:
		processed.add(i)
		for j in edges[i]:
			if j in nxt:
				k = i
				while k != j:
					l = nxt[k]
					del nxt[k]
					k = l
				nxt[i] = j
		i = nxt[i]
	start = i
	ret = [i]
	i = nxt[i]
	while i != start:
		ret.append(i)
		i = nxt[i]
	return ret
cycle = None
visited = {}
for start in range(n):
	if start not in visited:
		cycle = find_loop(start, visited, [])
		if cycle:
			break
if cycle:
	ret = find_local_minimum(cycle)
	print(len(ret))
	for i in ret:
		print(i + 1)
else:
	print(-1)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
edge = [[] for _ in [0] * n]
back = [[] for _ in [0] * n]
for _ in [0] * m:
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)
	back[b - 1].append(a - 1)
res = [None] * (n + 1)
for end in range(n):
	for start in edge[end]:
		cost = [-1] * n
		cost[start] = 0
		new = [start]
		tank = []
		judge = True
		while len(new) > 0 and judge:
			tank = []
			for fr in new:
				for go in edge[fr]:
					if cost[go] < 0:
						cost[go] = cost[fr] + 1
						tank.append(go)
						if go == end:
							judge = False
			new = tank
		if cost[end] >= 0 and cost[end] < len(res):
			p = end
			res = [p + 1]
			while p != start:
				for e in back[p]:
					if cost[p] == cost[e] + 1:
						p = e
						res.append(p + 1)
						break
if res[0] == None:
	print(-1)
else:
	print(len(res))
	for e in res:
		print(e)


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)


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

def cycle(E, visited):
	path_set = [False] * N
	path = []

	def dfs(v):
		if path_set[v]:
			path.append(v)
			return True
		if visited[v]:
			return False
		visited[v] = True
		path.append(v)
		path_set[v] = True
		for u in E[v]:
			if dfs(u):
				return True
		path.pop()
		path_set[v] = False
		return False
	while True:
		try:
			v = visited.index(False)
			if dfs(v):
				return path[path.index(path[-1]):-1]
		except ValueError:
			return None
c = cycle(E, [False] * N)
if c is None:
	print(-1)
	exit()
while True:
	c_set = set(c)
	cnt = 0
	for u in c:
		E[u] = [v for v in E[u] if v in c_set]
		shuffle(E[u])
		cnt += len(E[u])
	if cnt == len(c):
		break
	else:
		visited = [True] * N
		for v in c:
			visited[v] = False
		c = cycle(E, visited)
print(len(c))
for u in c:
	print(u + 1)


(n, m) = map(int, input().split())
g = [[] for _ in range(1005)]
for i in range(m):
	(a, b) = map(int, input().split())
	g[a].append(b)
vis = [0] * 1005

def dfs(x, p):
	if vis[x]:
		return []
	p.append(x)
	vis[x] = 1
	for v in g[x]:
		if v in p:
			return p
		t = dfs(v, p)
		if len(t):
			return t
	p.pop()
	return []
tmp = 0
ans = 10 ** 10
tmpp = []
p = []
vs = [0] * 1005

def dfs2(x):
	global ans, p, tmp, tmpp
	if len(p) >= ans:
		return
	p.append(x)
	for v in g[x]:
		if v == tmp:
			ans = len(p)
			tmpp = p[:]
			continue
		if not vs[v]:
			vs[v] = 1
			dfs2(v)
	p.pop()
a = []
for i in range(1, 1 + n):
	tmp = i
	p = []
	vs = [0] * 1005
	dfs2(i)
	if len(tmpp) == ans:
		a = tmpp[:]
if not len(a):
	print(-1)
	exit(0)
print(len(a))
for i in a:
	print(i)


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)


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)


def dijkstra_back(s, t, n, w, cost):
	import heapq
	prev = [s] * n
	d = [float('inf')] * n
	used = [False] * n
	d[s] = 0
	q = []
	heapq.heapify(q)
	heapq.heappush(q, (0, s))
	while q:
		(c, v) = heapq.heappop(q)
		if d[v] < c:
			continue
		for i in range(len(to[v])):
			k = to[v][i]
			if d[k] > d[v] + cost[v][k]:
				d[k] = d[v] + cost[v][k]
				heapq.heappush(q, (d[k], k))
				prev[k] = v
	path = [t]
	while prev[t] != s:
		path.append(prev[t])
		prev[t] = prev[prev[t]]
	path.append(s)
	path = path[::-1]
	return path
(N, M) = map(int, input().split())
fr = {i: [] for i in range(1, N + 1)}
to = {i: [] for i in range(1, N + 1)}
cost = [[float('inf') for i in range(0, N + 1)] for i in range(0, N + 1)]
for i in range(0, M):
	(a, b) = map(int, input().split())
	cost[a][b] = 1
	fr[b].append(a)
	to[a].append(b)
ansc = 10 ** 10
ans = []
for i in range(1, N + 1):
	for j in fr[i]:
		test = dijkstra_back(i, j, N + 1, M, cost)
		if len(test) == 2:
			if cost[i][j] != float('inf'):
				ansc = 2
				ans = test
		elif len(test) < ansc:
			ansc = len(test)
			ans = test
if ansc != 10 ** 10:
	print(ansc)
	for i in range(0, ansc):
		print(ans[i])
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)


import sys
input = sys.stdin.readline
import math
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
MOD = 10 ** 9 + 7
INF = float('inf')
AZ = 'abcdefghijklmnopqrstuvwxyz'

def I():
	return int(input().strip())

def S():
	return input().strip()

def IL():
	return list(map(int, input().split()))

def SL():
	return list(map(str, input().split()))

def ILs(n):
	return list((int(input()) for _ in range(n)))

def SLs(n):
	return list((input().strip() for _ in range(n)))

def ILL(n):
	return [list(map(int, input().split())) for _ in range(n)]

def SLL(n):
	return [list(map(str, input().split())) for _ in range(n)]

def DD(arg):
	return defaultdict(arg)

def inv(n):
	return pow(n, MOD - 2, MOD)
kaijo_memo = []

def kaijo(n):
	if len(kaijo_memo) > n:
		return kaijo_memo[n]
	if len(kaijo_memo) == 0:
		kaijo_memo.append(1)
	while len(kaijo_memo) <= n:
		kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
	return kaijo_memo[n]
gyaku_kaijo_memo = []

def gyaku_kaijo(n):
	if len(gyaku_kaijo_memo) > n:
		return gyaku_kaijo_memo[n]
	if len(gyaku_kaijo_memo) == 0:
		gyaku_kaijo_memo.append(1)
	while len(gyaku_kaijo_memo) <= n:
		gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD)
	return gyaku_kaijo_memo[n]

def nCr(n, r):
	if n == r:
		return 1
	if n < r or r < 0:
		return 0
	ret = 1
	ret = ret * kaijo(n) % MOD
	ret = ret * gyaku_kaijo(r) % MOD
	ret = ret * gyaku_kaijo(n - r) % MOD
	return ret

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

def make_divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	return divisors

def make_primes(N):
	max = int(math.sqrt(N))
	seachList = [i for i in range(2, N + 1)]
	primeNum = []
	while seachList[0] <= max:
		primeNum.append(seachList[0])
		tmp = seachList[0]
		seachList = [i for i in seachList if i % tmp != 0]
	primeNum.extend(seachList)
	return primeNum

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a * b // gcd(a, b)

def count_bit(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count

def base_10_to_n(X, n):
	if X // n:
		return base_10_to_n(X // n, n) + [X % n]
	return [X % n]

def base_n_to_10(X, n):
	return sum((int(str(X)[-i - 1]) * n ** i for i in range(len(str(X)))))

def base_10_to_n_without_0(X, n):
	X -= 1
	if X // n:
		return base_10_to_n_without_0(X // n, n) + [X % n]
	return [X % n]

def int_log(n, a):
	count = 0
	while n >= a:
		n //= a
		count += 1
	return count
(N, M) = IL()
graph = {i: [] for i in range(N)}
for _ in range(M):
	(a, b) = IL()
	graph[a - 1].append(b - 1)
Q = [i for i in range(N)]
p = [None for i in range(N)]
heiro = []
while Q:
	state = [-1 for i in range(N)]
	Flag = 0
	s = Q.pop()
	if p[s] != None:
		continue
	p[s] = -1
	q = [s]
	while q:
		flag = 0
		x = q.pop()
		if x < 0:
			state[~x] = 0
			continue
		q.append(~x)
		for y in graph[x]:
			state[x] = 1
			if state[y] == -1:
				p[y] = x
				q.append(y)
			elif state[y] == 0:
				continue
			else:
				p[y] = x
				now = x
				while now != y:
					heiro.append(now)
					now = p[now]
				heiro.append(y)
				flag = 1
				break
		if flag:
			Flag = 1
			break
	if Flag:
		break

def graph_size(g):
	ret = 0
	for k in g:
		ret += len(g[k])
	return ret

def squeeze(l):
	check = [0 for i in range(N)]
	for i in l:
		check[i] = 1
	global graph
	edges = []
	subgraph = {k: [] for k in l}
	data = DD(lambda : DD(int))
	i = 0
	for k in l:
		for y in graph[k]:
			if check[y]:
				subgraph[k].append(y)
				edges.append([0, k, y])
				data[k][y] = i
				i += 1
	graph = subgraph
	s = l[0]
	i = data[p[s]][s]
	edges[i][0] = 1
	now = p[s]
	heiro = [s]
	while now != s:
		heiro.append(now)
		i = data[p[now]][now]
		edges[i][0] = 1
		now = p[now]
	if len(heiro) == len(edges):
		print(len(heiro))
		for x in heiro:
			print(x + 1)
		exit()
	else:
		for (b, k, y) in edges:
			if not b:
				p[y] = k
				now = p[y]
				heiro = [y]
				while now != y:
					heiro.append(now)
					now = p[now]
				squeeze(heiro)
if not heiro:
	print(-1)
else:
	squeeze(heiro)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
(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)

def dfs(v, o):
	for c in G[v]:
		if c == o:
			return [v]
	for c in G[v]:
		if visited[c]:
			continue
		visited[c] = True
		ret = dfs(c, o)
		if ret:
			return [v] + ret
for v in range(1, N + 1):
	visited = [False] * (N + 1)
	cur = dfs(v, v)
	if cur:
		break
else:
	print(-1)
	exit()
while True:
	cur_set = set(cur)
	unused = None
	for i in range(len(cur)):
		(u, v) = (cur[i], cur[(i + 1) % len(cur)])
		for c in G[u]:
			if c == v:
				continue
			elif c in cur_set:
				unused = (i, cur.index(c))
				break
	if not unused:
		break
	else:
		(t, s) = unused
		nxt = []
		i = s
		while i != t:
			nxt.append(cur[i])
			i = (i + 1) % len(cur)
		nxt.append(cur[t])
		cur = nxt
print(len(cur))
print(*cur, sep='\n')


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
(n, m) = LI()
edge = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = LI()
	edge[a - 1].append(b - 1)
visited = [False] * n

def dfs(s):
	if visited[s]:
		return True
	visited[s] = True
	for i in edge[s]:
		if dfs(i):
			return True
	visited[s] = False
	return False
for i in range(n):
	if dfs(i):
		print(0)
		break
else:
	print(-1)


import heapq

class Edge:

	def __init__(self, _to, _cost):
		self.to = _to
		self.cost = _cost

class Dijkstra:

	def __init__(self, V):
		self.G = [[] for i in range(V + 1)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add(self, _from, _to, _cost):
		self.G[_from].append(Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		que = []
		heapq.heapify(que)
		d = [10 ** 10] * (self._V + 1)
		par = [-1] * (self._V + 1)
		d[s] = 0
		heapq.heappush(que, (0, s))
		while que:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for e in self.G[v]:
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					par[e.to] = v
					heapq.heappush(que, (d[e.to], e.to))
		return (d, par)
(N, M) = map(int, input().split())
G = []
ans = []
now_dis = 10 ** 6
for i in range(M):
	(a, b) = map(int, input().split())
	G.append((a, b))
for i in range(M):
	graph = Dijkstra(N)
	for j in range(M):
		if j != i:
			graph.add(G[j][0], G[j][1], 1)
	(S, T) = (G[i][0], G[i][1])
	(d, par) = graph.shortest_path(T)
	if d[S] + 1 < now_dis:
		now_dis = d[S] + 1
		sub = []
		node = S
		while node != T:
			sub.append(node)
			node = par[node]
		sub.append(T)
		ans = sub
K = len(ans)
if K == 0:
	print(-1)
	exit()
print(K)
for x in ans:
	print(x)


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
(n, m) = map(int, input().split())
path = [set() for _ in range(n)]
pathr = [set() for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	path[a - 1].add(b - 1)
	pathr[b - 1].add(a - 1)

def bfs(start):
	que = deque()
	d = [1e+100] * 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] == 1e+100:
				que.append(nxt)
			d[nxt] = min(d[nxt], d[p] + 1)
	if d[start] == 1e+100:
		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)


(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)
vis = {}

def dfs(i):
	if i in vis:
		return vis[i]
	vis[i] = True
	for j in g[i]:
		if dfs(j):
			return True
	vis[i] = False
	return False
for i in range(n):
	if dfs(i):
		print(0)
		break
else:
	print(-1)