#include<bits/stdc++.h>
using namespace std;
vector<int>a[100005];
int n,m,u,v,vis[100005],dt;
struct node
{
    int u,v;
}s[1000005];
bool cmd(node x,node y)
{
    if(x.u!=y.u)
        return x.u<y.u;
    else
        return x.v<y.v;
}
void dfs(int k)
{
    if(dt==0)
        return;
    dt--;
    cout<<k<<" ";
    for(int i=1;i<=a[k][0];i++)
        if(!vis[a[k][i]])
        {
            vis[k]=1;
            dfs(a[k][i]);
        }
}
void bfs(int k)
{
    queue<int>q;
    q.push(k);
    while(!q.empty())
    {
        cout<<q.front()<<" ";
        q.pop();
        for(int i=1;i<=a[k][0];i++)
            if(!vis[a[k][i]])
            {
                q.push(a[k][i]);
                vis[a[k][i]]=1;
            }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>s[i].u>>s[i].v;
    sort(s+1,s+m+1,cmd);
    for(int i=1;i<=m;i++)
    {
        a[s[i].u][0]++;
        a[s[i].u][a[s[i].u][0]]=s[i].v;
    }
    dt=n;
    dfs(1);
    memset(vis,0,sizeof(vis));
    cout<<endl;
    bfs(1);
}