#include<bits/stdc++.h>
using namespace std;
bool used[300300];
int col[300300];
int fa[300300];
vector<int>g[300300],h[300300],v[300300];
int n,m,tot;
int deg[300300];
priority_queue<pair<int,int> >q;
vector<int>ans;
queue<int>qq;
void dfs(int x,int pa){
	used[x]=1;col[x]=col[pa];fa[x]=pa;
	for (auto y:g[x])if(y!=pa){
		if(used[y]==1);
		else h[x].push_back(y),dfs(y,x);
	}
}
int main(){
	cin>>n>>m;
	for (int i=1,x,y;i<=m;i++)
	cin>>x>>y,g[x].push_back(y),g[y].push_back(x);
	for (int i=1;i<=n;i++)
	if(used[i]==0)col[i]=++tot,dfs(i,i);
	for (int i=1;i<=n;i++)
	v[col[i]].push_back(i);

	for (int i=2;i<=tot;i++)
	if(v[i].size()>=(n+1)/2){
		vector<int>zong;
		for (int j=1;j<=tot;j++)
		if(j!=i)for (auto k:v[j])
		zong.push_back(k);
		reverse(zong.begin(),zong.end());
		for(int j=1;j<=n;j++)
		if(col[j]==i){
			deg[j]=h[j].size();
			if(!deg[j])qq.push(j);
		}
		while(qq.size()&&v[i].size()){
			int x=qq.front();qq.pop();
			ans.push_back(zong.back());
			ans.push_back(x);
			zong.pop_back();
			deg[fa[x]]--;
			if(deg[fa[x]]==0)qq.push(fa[x]);
			if(!zong.size())break;
			
		}
		while(qq.size()>1){
			int x=qq.front();qq.pop();
			if(ans.size()&&fa[ans.back()]==x){
				qq.push(x);
				if(qq.size()==1)break;
				else continue; 
			}
			ans.push_back(x);
			deg[fa[x]]--;
			if(deg[fa[x]]==0)qq.push(fa[x]);
		}
		if(qq.size()){
		int x=qq.front();
		while(x!=ans.back()){
			ans.push_back(x);
			x=fa[x];
		}}
//		cout<<i<<"&&&\n";
		for (auto i:ans)
		cout<<i<<" ";cout<<"\n";
		return 0;
	}

	for (int i=2;i<=tot;i++)
	q.push({v[i].size(),i});
	while(q.size()>2){
		int x=q.top().second;q.pop();
		int y=q.top().second;q.pop();
		if(!v[x].size()||!v[y].size())break;
		ans.push_back(v[x].back());
		ans.push_back(v[y].back());
		v[x].pop_back(),v[y].pop_back();
		q.push({v[x].size(),x});
		q.push({v[y].size(),y}); 
	}
	for (int i=2;i<=tot;i++)
	if(v[i].size()){	
		for(int j=1;j<=n;j++)
		if(col[j]==1){
			deg[j]=h[j].size();
			if(!deg[j])qq.push(j);
		}
		while(qq.size()&&v[i].size()){
			int x=qq.front();qq.pop();
			ans.push_back(v[i].back());
			ans.push_back(x);
			v[i].pop_back();
			deg[fa[x]]--;
			if(deg[fa[x]]==0)qq.push(fa[x]);
			if(!v[i].size())break;
			
		}
		while(qq.size()>1){
			int x=qq.front();qq.pop();
			if(ans.size()&&fa[ans.back()]==x){
				qq.push(x);
				if(qq.size()==1)break;
				else continue; 
			}
			ans.push_back(x);
			deg[fa[x]]--;
			if(deg[fa[x]]==0)qq.push(fa[x]);
		}	
		
		if(qq.size()){
			int x=qq.front();
			while(x!=1){
				ans.push_back(x);
				x=fa[x];
			}
			ans.push_back(1);
		}
		
		for (int i=ans.size()-1;~i;i--)
		cout<<ans[i]<<" ";cout<<"\n";
	
		return 0;
	}
	for(int j=1;j<=n;j++)
	if(col[j]==1){
		deg[j]=h[j].size();
		if(!deg[j])qq.push(j);
	}

	while(qq.size()>1){
		int x=qq.front();
//		if(x==1)break;
		qq.pop();
		if(ans.size()&&fa[ans.back()]==x){
			qq.push(x);
			if(qq.size()==1)break;
			else continue; 
		}
		ans.push_back(x);
		deg[fa[x]]--;
		if(deg[fa[x]]==0)qq.push(fa[x]);
	}
	int x=qq.front();
	while(x!=1){
		ans.push_back(x);
		x=fa[x];
	}
	ans.push_back(1);
	for (int i=ans.size()-1;~i;i--)
	cout<<ans[i]<<" ";cout<<"\n";
}