#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<limits.h>
#include<stack>
#include<cstdlib>
#include<queue>
#include<map>
#include<vector>

#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

using namespace std;

int n,m;

queue<int> ref;

void DFS(int);
void BFS(int);
//bool isConnected(int,int);

vector<int>graph[100005];
bool flag[100005];

int main()
{
	IOS;
	cin>>n>>m;
	int x,y;
	memset(graph,false,sizeof(graph));
	while(m--)
	{
		cin>>x>>y;
		graph[x].push_back(y);
	}
	for(int i=1;i<=n;++i)sort(graph[i].begin(),graph[i].end());
	memset(flag,true,sizeof(flag));
	DFS(1);
	cout<<'\n';
	memset(flag,true,sizeof(flag));
	BFS(1);
 	return 0;
}
/*
bool isConnected(int x,int y)
{
	int i=0;
	while(i<graph[x].size())
	{
		if(graph[x][i]==y)return true;
		++i;
	}
	return false;
}
*/
void DFS(int x)
{
	cout<<x<<' ';
	for(int i=0;i<graph[x].size();++i)
	{
		if(flag[graph[x][i]])
		{
			flag[graph[x][i]]=false;
			DFS(graph[x][i]);
		}
	}
}

void BFS(int x)
{
	ref.push(x);
here:
	for(int i=0;i<graph[x].size();++i)
	{
		if(flag[graph[x][i]])
		{
			flag[graph[x][i]]=false;
			ref.push(graph[x][i]);
		}
	}
	cout<<ref.front()<<' ';
	ref.pop();
	if(!ref.empty()){
		x=ref.front();
		goto here;	
	}
}