#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+1,M = 1e5 + 1;
using pii = pair<int,int>;
int n,m,a,b,e[N],ne[N],h[M],idx = 0;
vector<pii> v;
bool cmp(const pii& a,const pii& b)
{
    if(a.first != b.first) return a.first<b.first;
    else return a.second < b.second;
}
void add(int a,int b)
{
    e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
void dfs(int x,bool st[])
{
    if(st[x]) return;
    cout << x << " ";
    st[x] = true;
    for(int i = h[x];i != -1; i = ne[i]){
        int j = e[i];
        if(st[j]) continue;
        dfs(j,st);
    }
    return;
}
void bfs(int x,bool st[])
{
    queue<int> q;
    q.push(x);
    st[x] = true;
    while(q.size()){
        int x = q.front();
        cout << x << " ";
        q.pop();
        for(int i = h[x];i!=-1;i=ne[i]){
            int j = e[i];
            if(st[j]) continue;
            q.push(j);
            st[j] = true;
        }
    }
}
int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--){
        cin >> a >> b;
        v.push_back({a,b});
    }
    sort(v.begin(),v.end(),cmp);
    while(v.size()){
        pii x = v.back();
        v.pop_back();
        add(x.first,x.second);
    }
    bool st[N] = {false}; // 初始化为 false
    bool stt[N] = {false}; // 初始化为 false
    dfs(1,st);
    cout << endl;
    bfs(1,stt);
    return 0;
}