#include<bits/stdc++.h> 
#include<vector>
#include<queue>
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define drep(i,a,b) for (int i=a; i<b; ++i)
using namespace std;
#define MAXN 114514
int n, m;
vector<int> G[MAXN];
queue<int> q;
bool visit[MAXN];
void dfs(int t){
    cout<<t<<" ";
    for (int i=0; i<G[t].size(); i++)
        if (!visit[G[t][i]]){
            visit[G[t][i]]=true;
            dfs(G[t][i]);
        }
}
void bfs(){
    visit[1]=1;
    q.push(1);
    while (!q.empty()){
        int a = q.front();
        cout<<a<<" ";
        for (int i=0; i<G[a].size(); i++){
            if (!visit[G[a][i]]){
                visit[G[a][i]]=true;
                q.push(G[a][i]);
            }
        }
        q.pop();
    }
}
int main(){
    cin>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        int a, b;
        cin>>a>>b;
        G[a].push_back(b);
    }
    for (int i=1; i<=n; ++i)
        sort(G[i].begin(),G[i].end());
    visit[1]=1;
    dfs(1);
    printf("\n");
    memset(visit,0,sizeof(visit));
    bfs();
    return 0;
}
/*
8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8
*/