#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define MAXN 100005
using namespace std;
int n, m;
vector <int> p[MAXN];
queue <int> q;
bool vis[MAXN];
void DFS(int x) {
    cout << x << " ";//输出小K看文献顺序
    int sz = p[x].size();
    for(int i = 0; i < sz; i++) {
        if(!vis[p[x][i]]) {
            vis[p[x][i]] = true;
            DFS(p[x][i]);
        }
    }
}
void BFS() {
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        cout << x << " ";
        int sz = p[x].size();
        for(int i = 0; i < sz; i++) {
            if(!vis[p[x][i]]) {
                vis[p[x][i]] = true;
                q.push(p[x][i]);
            }
        }
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int  x, y;
        cin >> x >> y;
        p[x].push_back(y);
    }
    for(int i = 0; i < n; i++) {
        sort(p[i].begin(), p[i].end());
    }
    vis[1] = true;
    DFS(1);
    cout << endl;
    memset(vis, false, 100005);
    vis[1] = true;
    q.push(1);
    BFS();
    cout << endl;
    return 0;
}