#include<stdio.h>
typedef struct Edge
{
	int u;
	int v;
}edge;
edge s[1000005];
int e[100001][1000];//e[i][j]表示起点为i的第j条边的序号 
int top[100001]={0};//记录e每个顶点有几条边 
int vis1[100001]={0};
int vis2[100002]={0};
int cmp(edge a,edge b)
{
	if(a.v==b.v)
		return a.u<b.u;
	return a.v<b.v;
}
void sort(int low,int high)
{
	edge x;
	int i,j;
	if(low>=high)
		return;
	if(low<high)
	{
		i=low;
		j=high;
		x=s[i];
		do
		{
			while(i<j&&!cmp(s[j],x))
				j--;
			if(i<j)
			{
				s[i]=s[j];
				i++;
				while(i<j&&cmp(s[i],x))
					i++;
				if(i<j)
				{
					s[j]=s[i];
					j--;
				}
			}
		}while(i!=j);
	}
	s[i]=x;
	sort(low,i-1);
	sort(i+1,high);
}
void dfs(int x)
{
	vis1[x]=1;
	printf("%d ",x);
	for(int i=0;i<top[x];i++)
	{
		int point=s[e[x][i]].v;
		if(vis1[point]==0)
			dfs(point);
	}
}
void bfs(int x)
{
	int q[100001];
	int front=0;
	int rear=0;
	q[rear++]=x;
	printf("%d ",x);
	vis2[x]=1;
	while(front!=rear)
	{
		int k=q[front];
		for(int i=0;i<top[k];i++)
		{
			int point=s[e[k][i]].v;
			if(vis2[point]==0)
			{
				q[rear++]=point;
				printf("%d ",point);
				vis2[point]=1;
			}
		}
		front++;
	}
}
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		s[i].u=a;
		s[i].v=b;
	}
	sort(0,m-1);
//	for(int i=1;i<=m;i++)
//	{
//		int flag=0;
//		for(int j=0;j<m-i;j++)
//		{
//			if(cmp(s[j],s[j+1])==0)
//			{
//				edge k=s[j+1];
//				s[j+1]=s[j];
//				s[j]=k;
//				flag=1;
//			}
//		}
//		if(flag==0)
//			break;
//	}
	for(int i=0;i<m;i++)
		e[s[i].u][top[s[i].u]++]=i;
//	for(int i=0;i<m;i++)
//		printf("%d %d\n",s[i].u,s[i].v);
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=0;j<10;j++)
//			printf("%d ",e[i][j]);
//		printf("\n");
//	}
	dfs(1);
	printf("\n");
	bfs(1);
}