#include <iostream>
#include <string>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
using namespace std;
set <int> hb;
map <int, set <int>> x;
map <int, vector <int>> p;
int n, m, p1, p2, h = 1;
void dfs(int a)
{
    cout << a << " ";
    hb.insert(a);
    for (int i = 0; i < p[a].size(); i++)
    {
        if (!hb.count(p[a][i])) dfs(p[a][i]);
    }
}
void bfs(int a)
{
    queue <int> s, ns;
    s.push(a);
    while (!s.empty())
    {
        ns = s;
        while (!s.empty())
        {
            cout << s.front() << " ";
            s.pop();
        }
        while (!ns.empty())
        {
            hb.insert(ns.front());
            for (int i = 0; i < p[ns.front()].size(); i++)
            {
                if (!hb.count(p[ns.front()][i]))
                {
                    s.push(p[ns.front()][i]), hb.insert(p[ns.front()][i]);
                }
            }
            ns.pop();
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> p1 >> p2;
        x[p1].insert(p2);
        hb.insert(p2);
    }
    for (int i = 1; i < n; i++)
    {
        while (!x[i].empty())
        {
            p[i].push_back(*x[i].begin());
            x[i].erase(x[i].begin());
        }
    }
    for (int i = 1; i <= n; i++) if (!hb.count(i)) h = i;
    hb.clear();
    dfs(h);
    hb.clear();
    cout << "\n";
    bfs(h);
    
    return 0;
}