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:
import sys
input = sys.stdin.buffer.readline

def find_cycle(adj, start = 0):
    """
    有効グラフ上で、0-indexedが前提の実装。
    あれば、適当なサイクルをリストで返す。
    参考1: https://qiita.com/drken/items/a803d4fc4a727e02f7ba
    参考2: https://qiita.com/Kiri8128/items/2b0023bed9af642c751c
    """
    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]: #arrived but not finished -> a cycle exists.
                    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')