#include<bits/stdc++.h>
using namespace std;
int head[114514]={0},cnt=1,n,m;
bool v[114514]={false};
struct SB{
	int aa,bb;
	bool operator<(const SB &x)const{
		return x.bb<bb;
	}
}k[114514];
struct tree{
	int to,nt;
}egde[114514];
void add(int a,int b){
	egde[cnt].nt=head[a],egde[cnt].to=b,head[a]=cnt++;
}
void dfs(int x){
	v[x]=true;
	cout<<x<<" ";
	for(int i=head[x];i;i=egde[i].nt){
		int s=egde[i].to;
		if(!v[s])dfs(s);
	}
}
void bfs(){
	queue<int>hi;
	hi.push(1);
	v[1]=true;
	while(!hi.empty()){
		int ha=hi.front();
		hi.pop();
		cout<<ha<<" ";
		for(int i=head[ha];i;i=egde[i].nt){
			int s=egde[i].to;
			if(!v[s])v[s]=true,hi.push(s);
		}
	}
}
int main(){
	cin.tie(),cout.tie();
	cin>>n>>m;
	int z,x;
	for(int i=1;i<=m;i++)cin>>k[i].aa>>k[i].bb;
	sort(k+1,k+1+m);
	for(int i=1;i<=m;i++)add(k[i].aa,k[i].bb);
	dfs(1);
	cout<<endl;
	memset(v,false,n+12);
	bfs();
}