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

const int MAXN = 10005;
vector<int> adj[MAXN];
bool visited[MAXN];

void dfs(int u, vector<int>& result) {
    visited[u] = true;
    result.push_back(u);
    
    for (int v : adj[u]) {
        if (!visited[v] && v >= 1 && v <= MAXN) {
            dfs(v, result);
        }
    }
}

vector<int> bfs(int start, int n) {
    vector<int> result;
    queue<int> q;
    fill(visited, visited + MAXN, false);
    
    if (start < 1 || start > n) return result;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);
        
        for (int v : adj[u]) {
            if (!visited[v] && v >= 1 && v <= n) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    if (!(cin >> n >> m)) return 0;
    
    if (n <= 0 || n > 1000 || m < 0 || m > 10000) return 0;
    
    for (int i = 0; i < m; i++) {
        int u, v;
        if (!(cin >> u >> v)) return 0;
        if (u >= 1 && u <= n && v >= 1 && v <= n) {
            adj[u].push_back(v);
        }
    }
    
    for (int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end());
    }
    
    vector<int> dfs_result;
    fill(visited, visited + MAXN, false);
    dfs(1, dfs_result);
    
    vector<int> bfs_result = bfs(1, n);
    
    for (size_t i = 0; i < dfs_result.size(); i++) {
        if (i > 0) cout << " ";
        cout << dfs_result[i];
    }
    cout << endl;
    
    for (size_t i = 0; i < bfs_result.size(); i++) {
        if (i > 0) cout << " ";
        cout << bfs_result[i];
    }
    cout << endl;
    
    return 0;
}