#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n,m;
struct Node{
	int s,e;
	bool operator<(Node a){
		if(s==a.s)return e<a.s;
		return s<a.s; 
	}
};
vector<Node>edge;
vector<int>a[100009];
int h[100009];
void dfs(int q){
	h[edge[i].e]=1;
	cout<<q<<' ';
	for(auto i:a[q]){
		if(h[edge[i].e]==0)dfs(edge[i].e);
	}
}
int bk[10000009],head,tail;
void bfs(){
	memset(h,0,sizeof(h));
	bk[tail++]=1;h[1]=1;
	while(head<tail){
		printf("%d ",bk[head]);
		for(auto i:a[bk[head]])
			if(h[edge[i].e]==0)bk[tail++]=edge[i].e,h[edge[i].e]=1;
		head++;
	}
}
int main(){
	cin>>n>>m;
	while(m--){
		int x,y;cin>>x>>y;
		edge.push_back(Node{x,y}); 
	}
	sort(edge.begin(),edge.end());
	for(int i=0;i<edge.size();i++)
		a[edge[i].s].push_back(i); 
	dfs(1);
	puts("");
	bfs();
}

P5318