#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int arr[N], idx;
vector<int> linker[N];
bool st[N];
int n, m, ans;

void dfs(int x) {

    arr[idx++] = x;
    for (int i = 0; i < linker[x].size(); i++) {
        int j = linker[x][i];
        if (!st[j]) {
            st[j] = 1;
            dfs(j);
        }
    }
}

void bfs(int x) {
    queue<int> qu;
    qu.push(x);
    arr[idx++] = x;
    while (qu.size()) {
        auto temp = qu.front();
        qu.pop();
        for (int i = 0; i < linker[temp].size(); i++) {
            int j = linker[temp][i];
            if (!st[j]) {
                st[j] = 1;
                arr[idx++] = j;
                qu.push(j);
            }
        }
    }
    for (int i = 0; i < idx; i++) {
        cout << arr[i] << " ";
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        linker[a].push_back(b);
    }
    for (int i = 1; i <= n; i++)sort(linker[i].begin(), linker[i].end());

    dfs(1);
    for (int i = 0; i < idx; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    memset(st, 0, sizeof st);
    idx = 0;
    bfs(1);
}