代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cctype>
#include<vector>
#define ll long long
#define rt register int
#define r read()
#define l putchar('\n')
ll read(){
	ll x=0;char ch=getchar(),zf=1;
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),zf=-1;
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return x*zf;
}
void write(ll x){if(x<0)putchar('-'),x=-x;if(x>=10)write(x/10);putchar(x%10+'0');}
void writeln(ll x){write(x);l;}
using namespace std;
int i,j,k,m,n,x,y,z,cnt;
#define M 500010
vector<int>ed[M];
int d[M],q[M],son[M];bool inh[M],vis[M];
void add(int x,int y){
	d[y]++;
	ed[x].push_back(y);
}
namespace subtask1{
	void dfs(int x,int pre){
		write(x),putchar(' ');
		int sz=ed[x].size();
		for(rt i=0;i<sz;i++)if(ed[x][i]!=pre)dfs(ed[x][i],x);
	}
	void calc(){
		for(rt i=1;i<=n;i++)sort(ed[i].begin(),ed[i].end());
		dfs(1,1);exit(0);
	}
}
namespace subtask2{
	int la=999999,fla=1,beg=0;
	void dfs(int x,int pre){
		if(!vis[x])write(x),putchar(' ');
		vis[x]=1;int sz=ed[x].size();		
		if(inh[x]&&!beg)beg=x;
		if(x==beg){
			for(rt i=0,tot=0,sl=0;i<sz;i++)if(!vis[ed[x][i]]){
				tot++;
				if(tot==1&&ed[x][i]!=son[x]&&!vis[son[x]])la=son[x];
				if(ed[x][i]!=son[x])sl++;
				if(sl==2){
					la=min(la,ed[x][i]);
					break;
				}
			}
		}
		int fir=0;
		for(rt i=0;i<sz;i++)if(!vis[ed[x][i]]){
			fir=ed[x][i];
			break;
		}
		if(fir==son[x]&&inh[x]&&son[x]&&!vis[son[x]])dfs(son[x],x);
		else if(son[x]&&x!=beg&&inh[x]&&!vis[son[x]])la=son[x];
		for(rt i=0;i<sz;i++){
			int u=ed[x][i];
			if(vis[u])continue;
			if(u>la&&fla){
				fla=0;
				return;
			}
			
			dfs(u,x);
		}
	}
	void calc(){
		for(rt i=1;i<=n;i++)sort(ed[i].begin(),ed[i].end());
		int h=0,t=0;for(rt i=1;i<=n;i++)inh[i]=1;
		for(rt i=1;i<=n;i++)if(d[i]==1)q[++t]=i,inh[i]=0;
		
		while(h<t){
			int u=q[++h];int sz=ed[u].size();
			for(rt i=0;i<sz;i++){
				d[ed[u][i]]--;son[ed[u][i]]=u;
				if(d[ed[u][i]]==1)q[++t]=ed[u][i],inh[i]=0;
			}
		}
		dfs(1,1);exit(0);
	}
}
int main(){
//	freopen("travel.in","r",stdin);freopen("travel.out","w",stdout);
	n=r;m=r;
	for(rt i=1;i<=m;i++){
		x=r;y=r;
		add(x,y);
		add(y,x);
	}
	if(m<n)subtask1::calc();
	subtask2::calc();
	return 0;
}

评测结果