#include <iostream>
#include <cstdio>
#include <algorithm>
#include<string.h>
using namespace std;
struct tu{
    int x,y;
}p[1000005];
int head[1000005],book[1000005],a[1000005],b[1000005];
bool cmp(struct tu a,struct tu b){
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
void dfs(int i,int a){
    cout<<a<<" ";
    for(i;p[i].x==a;i++)
        if(!book[p[i].y]){
            book[p[i].y]=1;
            dfs(head[p[i].y],p[i].y);
        }
    return;
}
void bfs(){
    int h=0,t=0,bb[1000005];
    bb[t++]=1;
    book[1]=1;
    while(t>h){
        cout<<bb[h]<<" ";
        for(int i=head[bb[h]];p[i].x==bb[h];i++)
            if(!book[p[i].y]){
                book[p[i].y]=1;
                bb[t++]=p[i].y;
            }
        h++;
    }
    return;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>p[i].x>>p[i].y;
        b[p[i].x]=1;
    }
    sort(p+1,p+m+1,cmp);
    for(int i=1;i<=m;i++)
        a[i]=p[i].x;
    for(int i=1;i<=n;i++)
        if(b[i])
            head[i]=lower_bound(a+1,a+m+1,i)-a;
    dfs(1,1);
    cout<<endl;
    memset(book,0,sizeof(book));
    bfs();
    return 0;
}