#include<bits/stdc++.h>
using namespace std;
int m,n,mp[10][10];
vector<int> g[100001];
queue<int> q;
bool vis[100005];
void bfs(int u)
{
	vis[1]=true;
	q.push(1);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		cout<<u<<" ";
		for(int v=0,sz=g[u].size();v<sz;v++)
		{
			if(!vis[g[u][v]])
			{
				vis[g[u][v]]=true;
				q.push(g[u][v]);
			}
		}
	}
}
int fa[100001];
void dfs(int u) 
{
	if(fa[u]) return;
	fa[u]=1;
	cout<<u<<" ";
  	for(int v:g[u]) dfs(v);
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++)
	{
		cin>>u>>v;
		g[u].push_back(v);
	}
	dfs(1);
	cout<<endl;
	vis[1]=true;
	bfs(1);
	return 0;
}