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 deque
n, m = map(int, input().split())
g = [[] for _ in range(n)]
INF = float('inf')
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)

res = []
shortest = n + 1
for s in range(n):
    dist = [-1] * n
    prev = [-1] * n
    q = deque()
    q.append(s)
    dist[s] = 0
    while len(q) != 0:
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                prev[nv] = v
                q.append(nv)
    for t in range(n):
        if t == s:
            continue
        if dist[t] == -1:
            continue
        for nt in g[t]:
            if nt == s:
                temp = [s]
                cur = t
                while cur != s:
                    temp.append(cur)
                    cur = prev[cur]
                if shortest > len(temp):
                    shortest = len(temp)
                    res = temp
if shortest == n + 1:
    print(-1)
    exit()
print(len(res))
for v in res:
    print(v + 1)

# def bfs(sv):
#     dist = [INF] * n
#     pre = [-1] * n
#     q = deque()
#     q.append(sv)
#     dist[sv] = 0
#     while q:
#         v = q.popleft()
#         for nv in g[v]:
#             if dist[nv] == INF:
#                 continue
#             pre[nv] = v
#             dist[nv] = dist[v] + 1
#             q.append(nv)
#     print(dist)
#     best = (INF, -1)
#     for v in range(n):
#         if v == sv:
#             continue
#         for nv in g[v]:
#             if nv == sv:
#                 best = min(best, (dist[nv], nv))
#                 print(sv, best)
#                 # print(best)
#     if best[0] == INF:
#         return [0] * (n + 1)
#     print(pre)
#     v = best[1]
#     print('v', v)
#     res = []
#     while v != -1:
#         res.append(v)
#         v = pre[v]
#     print('res', res)
#     return res


# ans = [0] * (n + 1)
# for s in range(n):
#     now = bfs(s)
#     if len(now) < len(ans):
#         print('aa')
#         ans = now
#         print(ans)
# if len(ans) == n + 1:
#     print(-1)
#     exit()
# print(len(ans))
# for v in ans:
#     print(v)