#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>

using namespace std;

const int MAXN = 100000;

vector<pair<int, int>> edge;
map<int, vector<pair<int, int>>::iterator> head;

int n, m, u, v;
bool vis[MAXN];

void match() {
    int tmp = 0;
    for (auto iter = edge.begin(); iter != edge.end(); iter++) {
        if (iter -> first != tmp) {
            head[iter -> first] = iter;
            tmp = iter -> first;
        }
    }
}

void dfs(int x) {
    vis[x] = 1;
    printf("%d ", x);
    if (head.count(x))
        for (auto iter = head[x]; iter -> first == head[x] -> first; iter++)
            if(!vis[iter -> second]) {
                dfs(iter -> second);
            }
}

void bfs(int x) {
    queue<int> q;
    q.push(x);
    printf("%d ", x);
    while(!q.empty()) {
        int f = q.front();
        if (head.count(f))
            for(auto iter = head[f]; iter -> first == head[f] -> first; iter++) {
                if (!vis[iter -> second]) {
                    int to = iter -> second;
                    q.push(to);
                    printf("%d ", to);
                    vis[iter -> second] = 1;
                }
            }
        q.pop();
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        edge.push_back(make_pair(u, v));
    }
    sort(edge.begin(), edge.end());
    match();
    dfs(1);
    puts("");
    memset(vis, 0, sizeof(vis));
    bfs(1);
    return 0;
}