#include<iostream>
#include<queue>
#include<cstring>
#define maxn 100005
using namespace std;
int head[maxn],ver[maxn],nest[10*maxn],eno;
int visiteddfs[maxn];
int visitedbfs[maxn];
int m,n;
void addedge(int a,int b) {//插入同时进行排序
	if(!head[a]) {//该节点还没有邻接点 
		eno++;
		ver[eno]=b;
		nest[eno]=head[a];
		head[a]=eno;
	} else {
		int record;//记录邻接表中的前一个点 
		int i;
		for(i=head[a]; i; i=nest[i]) {
			if(b<ver[i]) {
				if(i==head[a]) {//插入表头 
					eno++;
					ver[eno]=b;
					nest[eno]=head[a];
					head[a]=eno;
					break;
				} else { 
					eno++;
					ver[eno]=b;
					nest[record]=eno;
					nest[eno]=i;
					break;
				}
			}
			record=i;
		}
		if(!i) {//插入表尾 
			eno++;
			ver[eno]=b;
			nest[record]=eno;
			nest[eno]=i;
		}
	}
}
void dfs(int s) {
	visiteddfs[s]=1;
	printf("%d ",s);
	for(int i=head[s]; i; i=nest[i]) {
		if(visiteddfs[ver[i]]) continue;
		dfs(ver[i]);
	}
}
void bfs() {
	queue<int> Q;
	visitedbfs[1]=1;
	Q.push(1);
	while(!Q.empty()) {
		int s=Q.front();
		printf("%d ",s);
		Q.pop();
		for(int i=head[s]; i; i=nest[i]) {
			if(visitedbfs[ver[i]]) continue;
			visitedbfs[ver[i]]=1;
			Q.push(ver[i]);
		}
	}
}
int main() {
	memset(visiteddfs,0,sizeof(visiteddfs));
	memset(visitedbfs,0,sizeof(visitedbfs));
	cin>>n>>m;
	int a,b;
	for(int i=1; i<=m; i++) {
		scanf("%d %d",&a,&b);
		addedge(a,b);
	}
	dfs(1);
	putchar('\n');
	bfs();
	return 0;
}