#include<iostream>
using namespace std;
int from[2000001],to[2000001];  
void qsort(int l,int r)
{
    int i=l,j=r;
    do
    {
        while (from[i]<from[(l+r)/2] || (from[i]==from[(l+r)/2] && to[i]<to[(l+r)/2])) i++;
        while (from[j]>from[(l+r)/2] || (from[j]==from[(l+r)/2] && to[j]>to[(l+r)/2])) j--;
        if (i<=j)
        {
            int s=from[i];
            from[i]=from[j];
            from[j]=s;
            s=to[i];
            to[i]=to[j];
            to[j]=s;
            i++;
            j--;
        }
    }
    while (i<=j);
    if (l<j) qsort(l,j);
    if (i<r) qsort(i,r);
}
int n,m; 
struct node
{
    int data;
    node *next;
};
node* first[2000001];
bool flag[2000001];    
void dfs(int whe)
{   
    cout<<whe<<" ";
    node *p=first[whe];
    while (p!=NULL)
    {
        if (flag[p->data]==false)
        {   
            flag[p->data]=true;
            dfs(p->data);
        }
        p=p->next;
    }
}
int main()
{
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    cin>>from[i]>>to[i];
    qsort(1,m); 
    node *s=new node;
    s->data=to[1];
    s->next=NULL;
    first[1]=s;
    for (int i=2; i<=m; i++)
    {
        node *p=new node;
        p->data=to[i];
        p->next=NULL;
        if (from[i]==from[i-1])
        {   
            if (s!=NULL)
            s->next=p;
        }
        else
        {
            first[from[i]]=p;
        }
        s=p;
    }
    for (int i=1; i<=n; i++)
    flag[i]=false;
    flag[1]=true;
    dfs(1);
    cout<<endl;
    for (int i=1; i<=n; i++)
    flag[i]=false;
    cout<<1;
    int a[2000001];
    int qi=0,zhong=0;
    a[qi]=1;
    int step=1;
    flag[1]=false;
    while (step<n && qi<=zhong)
    {
        s=first[a[qi]];
        while (s!=NULL)
        {
            if (flag[s->data]==false)
            {
                flag[s->data]=true;
                cout<<" "<<s->data;
                zhong++;
                step++;
                a[zhong]=s->data;
            }
            s=s->next;
        }
        qi++;
    }
    return 0;
}