#include <bits/stdc++.h>

#define LL long long
#define PLL pair<LL,LL>

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	LL n,m,a,b;
	cin >> n >> m;
	vector<vector<LL>> g(n);
	vector<vector<LL>> gt(n);
	for (LL i = 0; i < m; i++){
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(b);
		gt[b].push_back(a);
	}
	vector<LL> res(3000,47);
	for (LL i = 0; i < n; i++){
		vector<LL> dist(n,5000);
		dist[i] = 0;
		vector<LL> prev(n);
		prev[i] = -1;
		vector<bool> closed(n,false);
		set<PLL> pq = {{0,i}};
		while (!pq.empty()){
			auto it = pq.begin();
			PLL curr = *it;
			pq.erase(it);
			if (closed[curr.second])
				continue;
			closed[curr.second] = true;
			for (LL v : g[curr.second]){
				if (dist[v] > curr.first+1){
					dist[v] = curr.first+1;
					prev[v] = curr.second;
					pq.insert({dist[v],v});
				}
			}
		}
		for (LL v : gt[i]){
			if (dist[v] > n)
				continue;
			if (dist[v]+1 < res.size()){
				res.clear();
				a = v;
				while (a >= 0){
					res.push_back(a);
					a = prev[a];
				}
			}
		}
	}
	if (res.size() > n){
		cout << "-1\n";
		return 0;
	}
	cout << res.size() << "\n";
	for (LL r : res)
		cout << r+1 << "\n";
}

### Prompt

Please formulate a Cpp solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>

#define LL long long
#define PLL pair<LL,LL>

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	LL n,m,a,b;
	cin >> n >> m;
	vector<vector<LL>> g(n);
	vector<vector<LL>> gt(n);
	for (LL i = 0; i < m; i++){
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(b);
		gt[b].push_back(a);
	}
	vector<LL> res(3000,47);
	for (LL i = 0; i < n; i++){
		vector<LL> dist(n,5000);
		dist[i] = 0;
		vector<LL> prev(n);
		prev[i] = -1;
		vector<bool> closed(n,false);
		set<PLL> pq = {{0,i}};
		while (!pq.empty()){
			auto it = pq.begin();
			PLL curr = *it;
			pq.erase(it);
			if (closed[curr.second])
				continue;
			closed[curr.second] = true;
			for (LL v : g[curr.second]){
				if (dist[v] > curr.first+1){
					dist[v] = curr.first+1;
					prev[v] = curr.second;
					pq.insert({dist[v],v});
				}
			}
		}
		for (LL v : gt[i]){
			if (dist[v] > n)
				continue;
			if (dist[v]+1 < res.size()){
				res.clear();
				a = v;
				while (a >= 0){
					res.push_back(a);
					a = prev[a];
				}
			}
		}
	}
	if (res.size() > n){
		cout << "-1\n";
		return 0;
	}
	cout << res.size() << "\n";
	for (LL r : res)
		cout << r+1 << "\n";
}

```