#include<bits/stdc++.h>
using namespace std;
int vis[100010]={0};
vector<int> edge[100010];
void dfs(int x)
{
	vis[x]=1;
	printf("%d ",x);
	for(int i=0;i<edge[x].size();i++)
	{
		int y=edge[x][i];
		if(vis[y]==0)
		{
			dfs(y);
		}
	}
}
void bfs(int x)
{
	queue<int> q;
	q.push(x);
	vis[x]=1;
	while(!q.empty())
	{
		int front=q.front();
		q.pop();
		printf("%d ",front);
		for(int i=0;i<edge[front].size();i++)
		{
			int y=edge[front][i];
			if(vis[y]==0)
			{
				q.push(y);
				vis[y]=1;
			}
		}
	}
}
int main()
{
	int n,m,uu,vv;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&uu,&vv);
		edge[uu].push_back(vv);
	}
	for(int i=1;i<=n;i++)
	{
		sort(edge[uu].begin(),edge[uu].end());
	}
	dfs(1);
	printf("\n");
	memset(vis,0,sizeof(vis));
	bfs(1);
	return 0;
}