#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 1000000
vector<int> a[MAXN];
bool vis[MAXN];
int n,x,y,maxx,m;
void dfs(int x){
    if(vis[x]) return;
    else vis[x]=1;
    cout<<x<<" ";
    for(int i=0;i<a[x].size();i++) dfs(a[x][i]);
}
void bfs(int num){
    int now;
    queue<int> x;
    x.push(num);
    while(!x.empty()){
        now=x.front();
        x.pop();
        if(vis[now]) continue;
        vis[now]=1;
        cout<<now<<" ";
        for(int i=0;i<a[now].size();i++){
            x.push(a[now][i]);
        }
    }
}
signed main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        a[x].push_back(y);
        maxx=max(maxx,x);
    }
    for(int i=1;i<=maxx;i++){
        sort(a[x].begin(),a[x].end());
    }
    dfs(1);
    fill(vis,vis+MAXN,0);
    cout<<endl;
    bfs(1);
    return 0;
}