#include<bits/stdc++.h>
using namespace std;
int cnt;
int n,m;
int x,y;
bool pd[110000];
bool pd1[110000];
struct edge{
	int to;
	int nxt;
}e[1100000];
int head[110000];
priority_queue<int,vector<int>,greater<int> >q;
void ad(int u,int v){
	cnt++;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
int read(){
	int r=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		r=r*10+c-'0';
		c=getchar();
	}
	return r;
}
void dfs(int x){
	cout<<x<<" ";
	int sum=0;
	int a[110000];
	for(int i=head[x];i;i=e[i].nxt){
		if(pd[e[i].to]==0){
			pd[e[i].to]=1;
			sum++;
			a[sum]=e[i].to;
		}
	}
	sort(a+1,a+1+sum);
	for(int i=1;i<=sum;i++){
		dfs(a[i]);
	}
}
void bfs(){
	q.push(1);
	while(!q.empty()){
		int now=q.top();
		q.pop();
		cout<<now<<" ";
		for(int i=head[now];i;i=e[i].nxt){
			if(pd1[e[i].to]==0){
				pd1[e[i].to]=1;
				q.push(e[i].to);
			}
		}
	}
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		x=read(),y=read();
		ad(x,y);
	}
	dfs(1);
	cout<<endl;
	bfs();
	return 0;
}