万能的谷民们

#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<cstdio>
#include<vector>
#include<ctime>
#include<unordered_map>
#include<map>
#include<cstdlib>
#include<iomanip>
#include<queue>
#include<set>
#include<stack>
#include<algorithm>
#include<fstream>
using namespace std;
stack<int> q;
int vis[5010];
int g[5010][5010];
int n,m;
int ans[5010];
int cnt;
int c=0;
int QAQ,QWQ;
int ccc;
int bbb;
int start;
int vvv[5010];
void Dfs1(int u,int fa)
{
	q.push(u);
	vis[u]=1;
	for(int i=1;i<=n;i++)
	{
		if(i==fa)
			continue;
		if(c==1)
			return;
		if(vis[i]&&g[u][i])
		{
			q.push(i);
			c=1;
			return;
		}
		if(g[u][i])
			Dfs1(i,u);
	}
}
void Dfs(int u,int fa)
{
	ans[++cnt]=u;
	if(vis[u]==2)
	{
		c;
		QWQ=u;
	}
	vvv[u]=1;
	for(int i=1;i<=n;i++)
	{
		if(vvv[i])
			continue;
		if(i==fa)
			continue;
		if(i==bbb)
			continue;
		int b=0;
		if(g[u][i]==1&&vis[i]&&vis[u]&&i>QAQ&&ccc==0)
		{
			ccc=1;
			b=i;
			bbb=u;
		}
		else if(g[u][i]==1)
		{
			Dfs(i,u);
		}
		if(b!=0&&u==QWQ)
		{
			Dfs(QAQ,QWQ);
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u][v]=1;
		g[v][u]=1;
	}
	Dfs1(1,0);
	memset(vis,0,sizeof(vis));
	while(q.size())
	{
		if(vis[q.top()])
		{
			vis[q.top()]=2;
			start=q.top();
			QAQ=q.top();
			break;
		}
		vis[q.top()]=1;
		q.pop();
	}
	if(QAQ==0)
		memset(vis,0,sizeof(vis));
	for(int i=n;i>=1;i--)
		if(vis[i]&&g[QAQ][i])
		{
			QAQ=i;
			break;
		}
	c=0;
	Dfs(1,0);
	for(int i=1;i<=cnt;i++)
		cout<<ans[i]<<" ";
	return 0;
}