#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
#define read(a) {char c;while((c=getchar())>47) a=a*10+(c^48);}
using namespace std;
int n, y, m;
int ans = 0;
int b[N];
vector<bool>vis;
vector<vector<int>>adj;

void dfs(int i)
{
    vis[i] = true;
    cout << i << " ";
    for (int j = 0; j < adj[i].size(); j++)
    {
        if (vis[adj[i][j]])
            continue;
        dfs(adj[i][j]);
    }
}
void bfs(int i)
{
    queue<int>q;
    q.push(i);
    while (!q.empty())
    {
       int s = q.front();
        vis[s] =false;
        cout << s << " ";
        for (int j = 0; j < adj[i].size(); j++)
        {
            if (vis[adj[i][j]])
            {
                vis[adj[i][j]] = false;
                q.push(adj[i][j]);
            }
       }
        i +=1;
        q.pop();

    }
    cout << endl;
}
int main()
{
    read(n);
    read(m);
    adj.resize(n + 1);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        read(a);
        read(b);
        adj[a].push_back(b);
    }
    for (int i = 1; i <= n; i++)
    {
        sort(adj[i].begin(), adj[i].end());
    }
    vis.resize(n + 1, false);
    dfs(1);
    cout << endl;
    bfs(1);
    return 0;
}