#include<bits/stdc++.h>
using namespace std;
vector<int> v[100001];
bool flag[100001];
int n,m;

void dfs(int n)
{
	cout<<n<<" ";
	for(int i=0;i<v[n].size();i++)
	{
		if(!flag[v[n][i]])
		{
			flag[v[n][i]]=1;
			dfs(v[n][i]);
		}
	}
}
void bfs(int n)
{
	int nobe[100001],head=0,tail=1;
	nobe[tail]=n;
	cout<<n<<" ";
	do
	{
		head++;
		for(int i=0;i<v[nobe[head]].size();i++)
		{
			int s=v[nobe[head]][i];
			if(!flag[s])
			{
				flag[s]=1;
				cout<<s<<" ";
				tail++;
				nobe[tail]=s;
			}
		}
	}while(head<tail);
} 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
	{
		sort(v[i].begin(),v[i].end());
	}
	dfs(1);
	cout<<endl;
	memset(flag,0,sizeof(flag));
	bfs(1);
	return 0;
}