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 JAVA):

Solution:
import java.util.*;

@SuppressWarnings("unchecked")
public class Main {
	static class Node {
		int value;
		Node next;
	}

	public static void printArray(int[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + ", ");
		}
		System.out.println();
	}

	// public static<T> void printArrayT(T[] a) {
	// 	for (int i = 0; i < a.length; i++) {
	// 		System.out.print(a[i] + ", ");
	// 	}
	// 	System.out.println();
	// }

	public static String joinInt(int[] a, String separator) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < a.length; i++) {
			if (i > 0) {
				sb.append(separator);
			}
			sb.append(a[i]);
		}
		return sb.toString();		
	}

	static int[] nextIntArray(Scanner sc, int N) {
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		return arr;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		ArrayList<Integer>[] edge = new ArrayList[N];
		for (int i = 0; i < M; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			append(edge, a, b);
		}
		int min = Integer.MAX_VALUE;
		int start = 0;
		for (int i = 0; i < N; i++) {
			int m = minLoop(i, edge);
			// System.out.println("min = " + m);
			if (m < min) {
				min = m;
				start = i;
			}
		}
		if (min == Integer.MAX_VALUE) {
			System.out.println(-1);
			return;
		}
		int[] prev = new int[N];
		Arrays.fill(prev, -1);
		Queue<Integer> q = new ArrayDeque<>();
		q.add(start);
		while (q.size() > 0 && prev[start] == -1) {
			int val = q.poll();
			if (edge[val] != null) {
				for (int next : edge[val]) {
					if (prev[next] == -1) {
						prev[next] = val;
						q.add(next);
					}
				}
			}
		}
		// System.out.println("start = " + start);
		// printArray(prev);
		int pos = start;
		int[] routes = new int[min];
		for (int i = min - 1; i >= 0; i--) {
			int p = prev[pos];
			routes[i] = p;
			pos = p;
		}
		System.out.println(min);
		for (int x : routes) {
			System.out.println(x + 1);
		}
	}

	static int minLoop(int start, ArrayList<Integer>[] edge) {
		int[] depth = new int[edge.length];
		depth[start] = 1;
		Queue<Integer> q = new ArrayDeque<>();
		q.add(start);
		while (q.size() > 0) {
			int val = q.poll();
			if (edge[val] != null) {
				int d2 = depth[val] + 1;
				for (int next : edge[val]) {
					if (next == start) {
						return d2 - 1;
					}
					if (depth[next] == 0) {
						depth[next] = d2;
						q.add(next);	
					}
				}
			}
		}
		return Integer.MAX_VALUE;
	}

	static void append(ArrayList<Integer>[] edge, int a, int b) {
		if (edge[a] == null) {
			edge[a] = new ArrayList<>();
		}
		edge[a].add(b);
	}
}