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


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


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

        if v == s:
            break

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

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

    return predecessors, circuit


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


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


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

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


n, m = 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)