#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
typedef struct {
	int u,v;
}pair;
pair pr[1000002];
typedef struct link{
	int k;
	struct link* next;
}linklist;
linklist g[100002];
int visit[100001];
int stack[100002];
int head=0,tail=0;
void dfs(int i){
	if(!visit[i]){
		visit[i]=1;
		printf("%d ",i);
		linklist *p=g[i].next;
		while(p){
			dfs(p->k);
			p=p->next;
		}
	}
}
int cmp(const void *a,const void *b){
	pair*aa=(pair*)a;
	pair*bb=(pair*)b;
	if(aa->v==bb->v)return aa->u-bb->u;
	return aa->v-bb->v;
}

void bfs(int i){
	stack[tail++]=i;
	visit[i]=1;
	printf("%d ",i);
	while(head<tail){
		int t=stack[head++];
		linklist*p=g[t].next;
		while(p){
			if(!visit[p->k]){
				printf("%d ",p->k);
				visit[p->k]=1;
				stack[tail++]=p->k;
			}
			p=p->next;
		}
	}
}
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		g[i].k=i;
		g[i].next=NULL;
	}
	for(int i=1;i<=m;i++)scanf("%d %d",&pr[i].u,&pr[i].v);
	pr[0].u=pr[0].v=0;
	qsort(pr,n+1,sizeof(pr[1]),cmp);
	for(int i=1;i<=m;i++){
		if(g[pr[i].u].next==NULL){
			linklist *p;
			p=(linklist*)malloc(sizeof(linklist));
			p->k=pr[i].v;
			p->next=NULL;
			g[pr[i].u].next=p;
		}
		else {
			linklist *p=g[pr[i].u].next,*q;
			while(p->next)p=p->next;
			q=(linklist*)malloc(sizeof(linklist));
			q->k=pr[i].v;
			q->next=NULL;
			p->next=q;
		
		}
	}
	dfs(1);
	memset(visit,0,sizeof(visit));
	printf("\n");
	bfs(1);
}