#include<stdio.h>
#include<string.h>
struct edge {
	int f,t;
} a[100010];
int e[10001][101]= {};
int el[100010];
int v1[100010]= {};
int v2[100010]= {};
int m,n;
void dfs(int x) {
	v1[x]=1;
	printf("%d ",x);
	for(int i=1; i<el[x]; i++) {
		int point=a[e[x][i]].t;
		if(!v1[point]) {
			dfs(point);
		}
	}
}
void bfs(int x) {
	int q[100010]={};
	int l=1,r=0;
	q[++r]=x;
	printf("%d ",x);
	v2[x]=1;
	while(l<=r) {  
		int fro=q[l];  //把队首取出来
		for(int i=1; i<el[fro]; i++) { //每条边去试
			int point=a[e[fro][i]].t;  //取终点（和dfs差不多）
			if(!v2[point]) { //没访问过，推进去，输出，标记
				q[++r]=point;
				printf("%d ",point);
				v2[point]=1;
			}
		}
		l++;
	}

}
int main() {

	int j=0;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; i++) {
		scanf("%d%d",&a[i].f,&a[i].t);
		if(a[i].f!=a[i-1].f)
			j=1;
		e[a[i].f][j++]=i;
		el[a[i].f]=j;
	}
	for(int i=1; i<=m; i++) {
		for(int j=1; j<el[i]; j++) {
			for(int k=el[i]-2; k>=j-1; k--) {
				if(e[i][k]>e[i][k+1]) {
					int tem=e[i][k];
					e[i][k]=e[i][k+1];
					e[i][k+1]=tem;
				}
			}
		}
	}
	dfs(1);
	printf("\n");
	bfs(1);
}