#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
vector<int> mp[N];
queue<int> q;
bool u[N],k[N];

void dfs(int x){
    cout << x << " " ;
    for(int i = 0;i < mp[x].size();i++){
        if(!u[mp[x][i]]){
            u[mp[x][i]] = true;
            dfs(mp[x][i]);
        }
    }
}

int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        int a,b;
        cin >> a >> b;
        mp[a].push_back(b);
    }
    u[1] = true;
    k[1] = true;
    dfs(1);
    cout << '\n';
    q.push(1);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        cout << x << ' ';
        for(int i = 0;i < mp[x].size();i++){
            if(!k[mp[x][i]]){
                k[mp[x][i]] = true;
                q.push(mp[x][i]);
            }
        }
    }
    return 0;
}