Description：

给一个有向图，求最小交替环。

$1\le n \le 5000$

Solution：

如果是带权图，那么可以 $\text{floyed}$ 求最小环，但是既然是不带权图，那么就枚举一个在环上的点，用 $\text{BFS}$ 找出的第一个环就是包含这个点的最小环，关于交替路怎么处理，直接建两个点 $a,a'$ ，每次连边 $a\to b'$ ，在这个无向二分图求无向图最小环即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

int type;

int n,m;

#define MAXN 5010

#define MAXM 1000010

struct edge

{

	int to,nxt;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN << 1] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

bool vis[MAXN << 1];

int fa[MAXN << 1];

int main()

{

	scanf("%d",&type);

	while(scanf("%d",&n) && n != 0)

	{

		edgenum = 0;

		memset(lin,0,sizeof(lin));

		scanf("%d",&m);

		int ans = -1;

		vector<int> res;

		int a,b;

		for(int i = 1;i <= m;++i)

		{

			scanf("%d%d",&a,&b);

			add(a,b + n);

		}

		for(int p = 1;p <= n;++p)

		{

			memset(vis,false,sizeof(vis));

			memset(fa,0,sizeof(fa));

			queue<int> q;

			q.push(p);vis[p] = true;

			vector<int> tmp;

			bool found = false;

			while(!q.empty())

			{

				int k = q.front();q.pop();

				for(int i = lin[k];i != 0;i = e[i].nxt)

				{

					if(vis[e[i].to] && e[i].to != fa[k])

					{

						found = true;

						while(k != p)

						{

							tmp.push_back(k);

							k = fa[k];

						}

						tmp.push_back(p);

						reverse(tmp.begin(),tmp.end());

						k = e[i].to;

						while(k != p)

						{

							tmp.push_back(k);

							k = fa[k];

						}

						found = true;

						break;

					}

					else if(!vis[e[i].to])

					{

						fa[e[i].to] = k;

						vis[e[i].to] = true;

						q.push(e[i].to);

					}

				}

				if(found)break;

			}

			if(!found)continue;

			if(ans == -1 || tmp.size() < res.size())

			{

				ans = tmp.size();

				res = tmp;

			}

		}

		cout << ans << endl;

		if(ans == -1)continue;

		for(int i = 0;i < res.size();++i)printf("%d ",(res[i] - 1) % n + 1);

		puts("");

	}

	return 0;

}