#include<set>
#include<vector>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<string>
#include<map>
using namespace std;

const int N = 1e4;

int e[N][N],book[1000000];
int n,m,sum=0;

struct note
{
    int city;
}que[10000000];
void bfs(int cur)
{
    int tail = 1, head = 1;
    que[tail].city = cur;
    tail++;
    book[cur] = 1;
    cout << cur << " ";
    while (head < tail)
    { 
        for (int k = 1; k <= n; k++)
        {
            if (e[cur][k] == 1&&book[k]==0)
            {
                cout << k << " ";
                book[k] = 1;
                que[tail].city = k;
                tail++;               
            }
        }        
        head++;
        cur = que[head].city;
    }
}
void dfs(int cur)
{
    cout << cur << " ";
    sum++;
    if (n == sum)
    {
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (e[cur][i] == 1 && book[i] == 0)
        {
            book[i] = 1;
            dfs(i);
            book[i] = 0;
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
            {
                e[i][j] = 0;
            }
            else
            {
                e[i][j] = 99999999;
            }
        }
    }

    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;

        e[a][b] = 1;
    }

    book[1] = 1;
    dfs(1);
    cout << endl;
    book[N] = { 0 };
    bfs(1);
    return 0;
}