#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef array<int,2> pr;
const int inf=1e9;
int n,m,bel[300005],cur,fa[300005],d[300005],used[300005],has[300005];
int ind[300005],rt[300005];
set<pr> comps;
map<int,int> hase[300005];
//fa,d:dfs tree
vector<int> g[300005],in[300005];
void dfs(int x){
	in[cur].push_back(x);
	bel[x]=cur;
	for(int y:g[x])if(!bel[y])d[y]=d[x]+1,fa[y]=x,dfs(y);
}
void D1(int x){
	comps.erase((pr){has[x],x});
	has[x]--;
	comps.insert((pr){has[x],x});
}
void Do(int x){
	while(used[in[x].back()])in[x].pop_back();
	cout<<in[x].back()<<' ';
	used[in[x].back()]=1;
	D1(x);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		g[x].push_back(y),g[y].push_back(x);
		hase[x][y]=hase[y][x]=1;
	}
	for(int i=1;i<=n;i++){
		if(bel[i])continue;
		++cur;
		rt[cur]=i;
		dfs(i);
		comps.insert((pr){has[cur]=in[cur].size(),cur});
	}
	int mxsz=(*--comps.end())[0],P=(*--comps.end())[1];
	if(mxsz<=n-mxsz+(P==1)){//1.直接构造 
		used[1]=1,D1(1),cout<<1<<' ';
		int cur=1;
		for(int i=1;i<n;i++){
			auto it=--comps.end();
			int mxp=(*it)[1];
			if(mxp!=cur){
				Do(mxp);
				cur=mxp;
			}
			else {
				--it;
				Do(cur=(*it)[1]);
			}
		}
		return 0;
	}
	if(P==1){//1是最大的 
		//puts("PP");
		int cnt=0;
		for(int i=1;i<=n;i++)if(bel[i]!=1)cnt++;
		//cnt个放成 [1,...,1,x,(1)1,x,(2)1]
		vector<int> ban;
		for(int i=1;i<=n;i++)if(bel[i]==1)ind[fa[i]]++;
		queue<int> q;
		for(int i=1;i<=n;i++)if(!ind[i]&&bel[i]==1)q.push(i);
		//cout<<cnt<<'\n';
		//puts("PP");
		for(int i=1;i<=cnt;i++){
			int x=q.front();
			q.pop();
			ban.push_back(x);
			used[x]=1;
			if(fa[x]&&!--ind[fa[x]])q.push(fa[x]);
		}
		//puts("PP");
		int mxd=-1,mxp=0;
		for(int i=1;i<=n;i++){
			//cout<<i<<'\n';
			if(!used[i]&&bel[i]==1&&d[i]>mxd){
				mxd=d[i];
				mxp=i;
			}
		}
		//cout<<mxp<<' '<<mxd<<'\n';
		vector<int> path;
		while(mxp){
			path.push_back(mxp);
			mxp=fa[mxp];
		}
		reverse(path.begin(),path.end());
		for(int i:path)cout<<i<<' ',used[i]=1;
		int lst=path.back();
		vector<int> pl;
		for(int i=1;i<=n;i++){
			if(bel[i]==1&&!used[i])pl.push_back(i);
		}
		sort(pl.begin(),pl.end(),[](int x,int y){return d[x]<d[y];});
		while(pl.size()){
			int x=pl.back();
			if(!hase[x][lst]){
				cout<<x<<' ';
				lst=x;
				pl.pop_back();
				continue;
			}
			else {
				assert(pl.size()>=2);
				assert(!hase[lst][pl[pl.size()-2]]);
				swap(pl[pl.size()-2],pl[pl.size()-1]);
				x=pl.back();
				cout<<x<<' ';
				lst=x;
				pl.pop_back();
			}
		}
		vector<int> oth;
		for(int i=1;i<=n;i++)if(bel[i]!=1)oth.push_back(i);
		for(int i=0;i<ban.size();i++){
			cout<<oth[i]<<' ';
			cout<<ban[i]<<' ';
		}
		return 0;
	}
	else {
		vector<int> oth;
		for(int i=1;i<=n;i++)if(bel[i]!=P)oth.push_back(i);
		int cnt=oth.size()-1;
		vector<int> ban;
		for(int i=1;i<=n;i++)if(bel[i]==P)ind[fa[i]]++;
		queue<int> q;
		for(int i=1;i<=n;i++)if(!ind[i]&&bel[i]==P)q.push(i);
		for(int i=1;i<=cnt;i++){
			int x=q.front();
			q.pop();
			ban.push_back(x);
			used[x]=1;
			if(fa[x]&&!--ind[fa[x]])q.push(fa[x]);
		}
		cout<<oth[0]<<' ';
		for(int i=0;i<ban.size();i++){
			cout<<ban[i]<<' ';
			cout<<oth[i+1]<<' ';
		}
		
		int mxd=-1,mxp=0;
		for(int i=1;i<=n;i++){
			if(!used[i]&&bel[i]==P&&d[i]>mxd){
				mxd=d[i];
				mxp=i;
			}
		}
		vector<int> path;
		while(mxp){
			path.push_back(mxp);
			mxp=fa[mxp];
		}
		reverse(path.begin(),path.end());
		vector<int> revans;
		for(int i:path)revans.push_back(i),used[i]=1;
		int lst=path.back();
		vector<int> pl;
		for(int i=1;i<=n;i++){
			if(bel[i]==P&&!used[i])pl.push_back(i);
		}
		sort(pl.begin(),pl.end(),[](int x,int y){return d[x]<d[y];});
		while(pl.size()){
			int x=pl.back();
			if(!hase[x][lst]){
				revans.push_back(x);
				lst=x;
				pl.pop_back();
				continue;
			}
			else {
				assert(pl.size()>=2);
				assert(!hase[lst][pl[pl.size()-2]]);
				swap(pl[pl.size()-2],pl[pl.size()-1]);
				x=pl.back();
				revans.push_back(x);
				lst=x;
				pl.pop_back();
			}
		}
		reverse(revans.begin(),revans.end());
		for(int i:revans)cout<<i<<' ';
		return 0;
	}
}