#include<bits/stdc++.h>
using namespace std;
int n,m,h[100001],b[100001],num,c[100001];
struct Edge
{
	int next;
	int to;
}edge[100001];
struct E
{
	int x,y;
}a[100001];
void add(int fr,int to)
{
	edge[++num].next=h[fr];
	edge[num].to=to;
	h[fr]=num;
}
bool cmp(E a,E b){
	if(a.x==b.x)
	return a.y>b.y;
	return a.x<b.x;
}
void BFS()
{
	queue<int>q;
	q.push(1);
	b[1]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		printf("%d ",x);
		for(int i=h[x];i;i=edge[i].next){
			int y=edge[i].to;
			if(b[y]) continue;
			b[y]=1;
			q.push(y);
		}
	}
}
void DFS(int x)
{
	c[x]=1;
	for(int i=h[x];i;i=edge[i].next)
	{
		int cnt=edge[i].to;
		if(c[cnt]==1)
		continue;
		printf("%d ",cnt);
		DFS(cnt);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=m;i++){
		add(a[i].x,a[i].y);
	}
printf("1 ");
DFS(1);
printf("\n");
BFS();
	return 0;
}