#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
queue<int>Q;
int n,m;
struct node{
	int n1 = 0;
	int num[10];
}a[100005];
int flag1[100005];
int flag2[100005];
void DFS(int x)
{
	cout<<x<<" ";
	//sort(a[x].num+1,a[x].num+1+a[x].n1);
	for(int i=1;i<=a[x].n1;i++)
	{
		if(flag1[a[x].num[i]]==0)
		{
			flag1[a[x].num[i]]=1;
			DFS(a[x].num[i]);
		}
	}
}

void bfs()
{
	while(!Q.empty())
	{
		int temp = Q.front();
		Q.pop();
		cout<<temp<<" ";
		//sort(a[temp].num+1,a[temp].num+1+a[temp].n1);
		for(int i=1;i<=a[temp].n1;i++)
		{
			if(flag2[a[temp].num[i]]==0)
			{
				flag2[a[temp].num[i]]=1;
				Q.push(a[temp].num[i]);
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int father,son;
		cin>>father>>son;
		a[father].n1++;
		a[father].num[a[father].n1]=son;
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i].n1>1)
		{
			sort(a[i].num+1,a[i].num+1+a[i].n1);
		}
	}
	flag1[1]=1;
	DFS(1);
	cout<<endl;
	flag2[1]=1;
	Q.push(1);
	bfs();
	
	
	return 0;
}