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:
#!/usr/bin/python3

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)


if __name__ == '__main__':
    main()