#include<bits/stdc++.h>
using namespace std;
int n,m;
long long g[10001][10001];//定义图 （邻接矩阵） 
int dfs_vis[10001];//在深搜中一个点是否访问过，是则为 1，否则为 0 
void dfs(int u)
{
    cout<<u<<" ";//输出访问的数 
    dfs_vis[u]=1;//标记已访问 
    for(int i=1;i<=n;i++)
      if(g[u][i]==1&&dfs_vis[i]==0)//相连且没访问的数 
        dfs(i);//递归 
}
int bfs_vis[10001];//在广搜中一个点是否访问过，是则为 1，否则为 0
int a[10001];//模仿队列 
void bfs(int u)
{
    int head=0,tail=1;//头与尾的指针 
    a[0]=u;//顶点入队 
    bfs_vis[u]=1;//标记已访问 
    while(head<tail)//判断队列是否为空 
    {
        int p=a[head++];//将队尾取出 
        cout<<p<<" ";
        for(int i=1;i<=n;i++)
          if(g[p][i]==1&&bfs_vis[i]!=1)//相连且没背访问过的数 
          {
              a[tail++]=i;//找到的数入队 
              bfs_vis[i]=1;//标记已访问 
          } 
    }
}
int main()
{
    int gi,gj;// 顶点（gi）和与之相连的顶点（gj）（邻接矩阵） 
    cin>>n>>m;//顶点数（n）  边数（m） 
    for(int i=1;i<=m;i++)//储存图 （邻接矩阵）
    {
        cin>>gi>>gj;// 输入 
        g[gi][gj]=1;//确定边 （根据题意，我认为这是有向图）
    }
    dfs(1);//深搜结果 
    cout<<endl;//换行 
    bfs(1);//广搜结果 
    return 0;//好习惯 
 }