代码

#include<bits/stdc++.h>
using namespace std;
inline void read(int &x){
	x = 0;
	int p = 1;
	char c = getchar();
	while(!isdigit(c)){
		if(c == '-')p = -1;
		c = getchar();
	}
	while(isdigit(c)){
		x = (x << 1) + (x << 3) + (c ^ '0');
		c = getchar();
	}
	x *= p;
}
const int maxn = 5050;
vector<int>vec[maxn];
int n, m;
namespace sub1{
	vector<int>ans;
	bool vis[maxn];
	inline void dfs(int u){
		vis[u] = 1;
		ans.push_back(u);
		for(register int i = 0, sz = vec[u].size(); i < sz; ++i){
			int v = vec[u][i];
			if(!vis[v])dfs(v);
		}
	}
	inline void solve(){
		memset(vis, 0, sizeof(vis));
		dfs(1);
		for(register int i = 0, sz = ans.size(); i < sz; ++i){
			printf("%d ", ans[i]);
		}
	}
}
namespace sub2{
	stack<int>sta;
	vector<int>cir, ans;
	bool flag = 0, cjump = 0, nowjump = 0, entcir = 0;
	bool vis[maxn], iscir[maxn];
	int beg, nxt[10], tot = 0;
	inline void circle(int fir){
		while(!sta.empty() && sta.top() != fir){
			int u = sta.top();
			cir.push_back(u);
			iscir[u] = 1;
			sta.pop();
		}
		cir.push_back(fir);
		iscir[fir] = 1;
		sta.pop();
	}
	inline void get_cir(int u, int fa){
		vis[u] = 1;
		sta.push(u);
		for(register int i = 0, sz = vec[u].size(); i < sz; ++i){
			int v = vec[u][i];
			if(v == fa)continue;
			if(flag)return ;
			if(vis[v]){
				circle(v);
				flag = 1;
				return ;
			}
			get_cir(v, u);
		}
		sta.pop();
	}
	inline void dfs(int u){
		//cerr<<u<<endl;
		vis[u] = 1;
		ans.push_back(u);
		if((!entcir) && iscir[u]){
			entcir = 1;
			beg = u;
			for(register int i = 0, sz = vec[u].size(); i < sz; ++i){
				if(iscir[vec[u][i]])nxt[++tot] = vec[u][i];
			}
			if(nxt[1] > nxt[2])swap(nxt[1], nxt[2]);
			cjump = 1;
		}
		for(register int i = 0, sz = vec[u].size(); i < sz; ++i){
			int v = vec[u][i];
			if(cjump && iscir[v] && v > nxt[2]){
				//cerr<<u<<":::"<<nxt[2]<<endl;
				cjump = 0, nowjump = 1;
				continue;
			}
			if(!vis[v])dfs(v);
		}
		if(nowjump){
			if(u != beg)return ;
			else nowjump = 0;
		}
	}
	inline void solve(){
		memset(vis, 0, sizeof(vis));
		get_cir(1, 0);
		/*for(register int i = 0, sz = cir.size(); i < sz; ++i){
			printf("%d ", cir[i]);
		}*/
		//puts("");
		memset(vis, 0, sizeof(vis));
		dfs(1);
		for(register int i = 0, sz = ans.size(); i < sz; ++i){
			printf("%d ", ans[i]);
		}
	}
}
int main(){
	read(n), read(m);
	int u, v;
	for(register int i = 1; i <= m; ++i){
		read(u), read(v);
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	for(register int i = 1; i <= n; ++i){
		sort(vec[i].begin(), vec[i].end());
	}
	if(m == n - 1)sub1::solve();
	else sub2::solve();
	return 0;
}

评测结果