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

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

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

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

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

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

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

cycle = find_cycle(g)

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