76pts求调

#include<bits/stdc++.h>
using namespace std;
int n,m,head[500005],tot,d[500005],vis[500005],num,t,in[500005],fl;
queue<int>	q;
struct sd{
	int ne,to;
}edge[1000005];
void add(int x,int y){
	edge[++tot].ne=head[x];
	edge[tot].to=y;
	head[x]=tot;
}
void dfs(int x,int fa){
//	printf("%d\n",x);
	d[++num]=x;
	vis[x]=1;
	vector<int>	vec;
	for(int i=head[x];i;i=edge[i].ne){
		int y=edge[i].to;
		if(in[y]!=1)	t=y;
		if(y==fa || in[y]!=1 || vis[y])	continue;
		vec.push_back(y);
	}
	sort(vec.begin(),vec.end());
	for(int i=0;i<vec.size();i++){
//		if(vis[vec[i]])	continue;
		dfs(vec[i],x);
	}
}
void solve(int x,int fa,int mi){
//	printf("%d\n",x); 
	d[++num]=x;
	vis[x]=1;
	vector<int>	vec;
	for(int i=head[x];i;i=edge[i].ne){
		int y=edge[i].to;
		if(y==fa || vis[y])	continue;
		vec.push_back(y);
	}
	sort(vec.begin(),vec.end());
	int flag=1e9,gg=0,cnt=0;
	for(int i=vec.size()-1;i>=0;i--){
		if(in[vec[i]]!=1){
			flag=vec[i];
			break;
		}
	}
	if(x!=t){
		if(flag!=1e9 && flag>mi && flag==vec[vec.size()-1] && !fl){
			for(int i=0;i<vec.size();i++)	if(in[vec[i]]==1)	dfs(vec[i],x);
			fl++; 
			return ;
		}
	}
	for(int i=0;i<vec.size();i++){
		if(vis[vec[i]])	continue;
		if(in[vec[i]]!=1)	solve(vec[i],x,((i+1<vec.size())?vec[i+1]:mi));
		else	dfs(vec[i],x);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
		in[x]++;
		in[y]++;
	}
	for(int i=1;i<=n;i++)	if(in[i]==1)	q.push(i);
	while(q.size()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=edge[i].ne){
			int y=edge[i].to;
			if(in[y]==1)	continue;
			if(--in[y]==1)	q.push(y);
		}
	}
	if(in[1]==1)	dfs(1,0);
	else	t=1;
//	printf("%d ",t);
	if(m==n)	solve(t,0,1e9);
	else if(!vis[1])	dfs(1,0); 
	for(int i=1;i<=num;i++)	printf("%d ",d[i]);
}