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

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.

Examples

Input

4 5
1 2
2 3
2 4
4 1
4 3


Output

3
1
2
4


Input

4 5
1 2
2 3
2 4
1 4
4 3


Output

-1


Input

6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2


Output

4
2
3
4
5

Solution (in PYTHON3):

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