#include<bits/stdc++.h>
using namespace std;
int n,m;
const int Max=1000001;
struct node
{
    int v;
    int w;
}temp;
vector<node> g[Max];
int dfs_vis[Max];
int bfs_vis[Max];
int a[Max];

void dfs(int u) {
    cout << u << " ";
    dfs_vis[u] = 1;
    for (int j=0;j<g[u].size();j++)
      if (dfs_vis[g[u][j].v] == 0)
        dfs(g[u][j].v);
}

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 j=0;j<g[p].size();j++)
            if (bfs_vis[g[p][j].v] == 0)
            {
                a[tail++] = g[p][j].v;
                bfs_vis[g[p][j].v] = 1;
            }
    }
}

int main()
{
    int start;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>start>>temp.v;
        g[start].push_back(temp);
    }
    dfs(1);
    cout<<endl;
    bfs(1);
    return 0;
}