#include<bits/stdc++.h>
using namespace std;
int a,dian,nxt,f,vis[100005],x;
vector<int> v[100005];
queue<int>q;
void dfs(int s)
{
	if(vis[s] == 1) return;
	printf("%d ",s);
	vis[s]=1;
	for(auto y:v[s]){
		dfs(y);	
	} 
} 
void bfs(int s)
{
	q.push(s);
	vis[s]=1;
	while(!q.empty()) 
	{
		x=q.front();
		printf("%d ",x);
		q.pop();
		for(auto y:v[x])
		{
			if(vis[y]==0) 
			{
				vis[y]=1;
				q.push(y);
			}
		}
	} 
}
int main()
{
	
	scanf("%d%d",&a,&f);
	for(int i=1;i<=f;i++)
	{
	    scanf("%d%d",&dian,&nxt);
		v[dian].push_back(nxt);
	}
	for(int i=1;i<=f;i++)
		sort(v[i].begin(),v[i].end()); 
	dfs(1);
	printf("\n");
	memset(vis, 0, sizeof(vis));
	bfs(1);
	return 0;
}