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 Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
# from copy import deepcopy, copy

import queue
from collections import deque


def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]

    graph_data = defaultdict(set)
    jisuu_list = [0 for i in range(node_num + 1)]
    for i in range(edge_num):
        a, b = data[i]
        graph_data[a].add(b)
        jisuu_list[b] += 1


    now_set = set()
    next_set = set()
    for i in range(1, node_num + 1):
        if jisuu_list[i] == 0:
            now_set.add(i)

    while len(now_set) > 0:
        for now_node in now_set:
            for next_node in graph_data[now_node]:
                jisuu_list[next_node] -= 1
                if jisuu_list[next_node] == 0:
                    next_set.add(next_node)
        now_set = next_set
        next_set = set()

    if max(jisuu_list) == 0:
        print(-1)
        sys.exit()

    ans = []
    dist = 10 ** 10
    for i in range(1, node_num + 1):
        if jisuu_list[i] == 0:
            continue

        parent_node = [0 for i in range(node_num + 1)]
        now_set = set()
        next_set = set()
        now_set.add(i)
        dist_kari = 0
        fin_flg = 0
        while len(now_set) > 0:
            dist_kari += 1
            # print(now_set, graph_data, fin_flg, parent_node)
            for now_node in now_set:
                for next_node in graph_data[now_node]:
                    # print('uuu', next_node)
                    if next_node == i:
                        parent_node[next_node] = now_node
                        fin_flg = 1
                        break
                    if jisuu_list[next_node] == 0:
                        continue
                    if parent_node[next_node] == 0:
                        parent_node[next_node] = now_node
                        next_set.add(next_node)
                if fin_flg:
                    break
            if fin_flg:
                break
            now_set = next_set
            next_set = set()

        if dist_kari < dist and fin_flg:
            dist = dist_kari
            ans = []
            now_node = parent_node[i]
            ans.append(i)
            # print(parent_node)
            while now_node != i:
                ans.append(now_node)
                now_node = parent_node[now_node]

    print(len(ans))
    for ele in ans:
        print(ele)







if __name__ == '__main__':
    main()