#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, vis[N];
vector<int> G[N];
queue<int> q;
void dfs(int u, int fa) {
    if (vis[u])  return ;
    vis[u] = 1;
    cout << u << " ";
    for (int v : G[u])  if (v != fa && ! vis[v])  dfs(v, u);
}
void bfs() {
    memset(vis, 0, sizeof(vis));
    q.push(1);
    while (! q.empty()) {
        int u = q.front();
        q.pop();
        if (vis[u])  continue;
        cout << u << " ";
        vis[u] = 1;
        for (int v : G[u])  q.push(v);
    }
}
int main() {
    cin >> n >> m;
    int a, b;
    for (int i = 1; i <= m; i ++ )  cin >> a >> b, G[a].push_back(b);
    dfs(1, 0);
    cout << endl;
    bfs();
    return 0;
}