#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e3 + 5;
const ll LINF = 1e18 + 5;
int n, m, pre[N];
vector <int> G[N], ans;
int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	cin >> n >> m;
 	for(int i=1; i<=m; i++)
 	{
 		int u, v;
 		cin >> u >> v;
 		G[u].pb(v);
 	}
 	for(int i=1; i<=n; i++)
 	{
 		memset(pre+1, 0, n*sizeof(int));
 		queue <int> q;
 		for(int v : G[i])
 		{
 			pre[v] = i;
 			q.push(v);
 		}
 		while(sz(q))
 		{
 			int u = q.front(); q.pop();
 			if(u==i)
 			{
 				vector <int> loop;
 				int x = pre[u];
 				while(x!=i)
 				{
 					loop.pb(x);
 					x = pre[x];
 				}
 				loop.pb(x);
 				if(!sz(ans) || sz(loop)<sz(ans)) swap(loop, ans);
 				break;
 			}
 			for(int v : G[u])
 			{
 				if(!pre[v])
 				{
 					pre[v] = u;
 					q.push(v);
 				}
 			}
 		}
 	}
 	if(sz(ans))
 	{
 		cout << sz(ans) << '\n';
 		reverse(all(ans));
 		for(int x : ans) cout << x << '\n';
 	}
 	else cout << -1 << '\n';
	return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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 mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e3 + 5;
const ll LINF = 1e18 + 5;
int n, m, pre[N];
vector <int> G[N], ans;
int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	cin >> n >> m;
 	for(int i=1; i<=m; i++)
 	{
 		int u, v;
 		cin >> u >> v;
 		G[u].pb(v);
 	}
 	for(int i=1; i<=n; i++)
 	{
 		memset(pre+1, 0, n*sizeof(int));
 		queue <int> q;
 		for(int v : G[i])
 		{
 			pre[v] = i;
 			q.push(v);
 		}
 		while(sz(q))
 		{
 			int u = q.front(); q.pop();
 			if(u==i)
 			{
 				vector <int> loop;
 				int x = pre[u];
 				while(x!=i)
 				{
 					loop.pb(x);
 					x = pre[x];
 				}
 				loop.pb(x);
 				if(!sz(ans) || sz(loop)<sz(ans)) swap(loop, ans);
 				break;
 			}
 			for(int v : G[u])
 			{
 				if(!pre[v])
 				{
 					pre[v] = u;
 					q.push(v);
 				}
 			}
 		}
 	}
 	if(sz(ans))
 	{
 		cout << sz(ans) << '\n';
 		reverse(all(ans));
 		for(int x : ans) cout << x << '\n';
 	}
 	else cout << -1 << '\n';
	return 0;
}

```