#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int n; // 结点数
int m; // 边数

int from;
int to;

vector<vector<int>> relations;
vector<bool> visited;

void dfs(int i) {
    cout << i << " ";
    visited[i] = true;
    for (int k: relations[i])
        if (!visited[k])
            dfs(k);
}

void bfs(int i) {
    queue<int> q;
    q.push(i);
    visited[i] = true;
    while (!q.empty()) {
        int front = q.front();
        q.pop();
        cout << front << " ";
        for (int k: relations[front]) {
            if (!visited[k]) {
                visited[k] = true;
                q.push(k);
            }
        }
    }
}


int main() {
    cin >> n >> m;
    relations = vector<vector<int>>(n + 1);
    visited = vector<bool>(n + 1);
    int cnt = m;
    while (cnt && cin >> from >> to) {
        relations[from].emplace_back(to);
        --cnt;
    }
    dfs(1);
    cout << endl;
    std::fill(visited.begin(), visited.end(), false);
    bfs(1);
    cout << endl;
};