（难道只有我一个人wa#2和#5！？）

#include<bits/stdc++.h>
using namespace std;
unsigned long long m,n;
vector<vector<unsigned long long>> b(5000000);
queue<unsigned long long> q;
unsigned long long u,v,sum;
int vis[1000000];
void dfs(unsigned long long x)
{
    vis[x]=1;
    sum++;
    cout<<x<<" ";
    if(!b[x].empty()&&x!=n)
    {
        for(int i=0;i<=b[x].size()-1;i++)
        {
            if(vis[b[x][i]]==0) dfs(b[x][i]);
        }
    }
}
void bfs()
{
    while(!q.empty())
    {
        unsigned long long z=q.front();
        cout<<z<<" ";
        q.pop();
        if(!b[z].empty())
        {
            for(int i=0;i<=b[z].size()-1;i++)
            {
                if(vis[b[z][i]]==1)
                {
                    vis[b[z][i]]=0;
                    q.push(b[z][i]);
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        b[u].push_back(v);
    }
    for(int i=1;i<=n;i++)
    {
        if(!b[i].empty()) sort(b[i].begin(),b[i].end());
    }
    dfs(1);
    q.push(1);
    cout<<endl;
    vis[1]=0;
    bfs();
    return 0;
}