#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,m,cnt;
bool vis[maxn];
vector<int>v[maxn];
void dfs(int x)
{
    if(cnt==n) return;
    cout<<x<<' ';
    cnt++;
    for(int i=0; i<v[x].size(); i++) dfs(v[x][i]);
}
void bfs(int x)
{
    queue<int>q;
    q.push(x);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        cout<<u<<' ';
        for(int i=0; i<v[u].size(); i++)
        {
            int t=v[u][i];
            if(!vis[t])
            {
                q.push(t);
                vis[t]=1;
            }
        }
    }
}
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;
    vis[1]=1;
    bfs(1);
	return 0;
}