#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
int h[N],e[M],ne[N],idx,res[N],cnt = 1, res1[N],cnt1 ;
int n,m;
bool st[N],vis[N];

struct node
{
 int dd,xx;
}nodes[M];
bool cmp(node x, node y)
{
    if(x.dd == y.dd && x.xx > y.xx) return true;
    return false;
}
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a],h[a] = idx++; 
}
void dfs(int x)
{   st[x] = true;
    res[0] = 1;
    for(int i = h[x]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(!st[j])
            {
             res[cnt++] = j;   
            dfs(j);
            }
        }
    return;
}
void bfs()
{
	queue<int> q;
	vis[1] = true;
	q.push(1);
	while(q.size())
	{
		res1[cnt1++] = q.front();
		int t = q.front();
		q.pop();
		for(int i = h[t]; i!= -1;i = ne[i])
		{
			int j = e[i];
			if(!vis[j])
			{
				vis[j] = true;
				q.push(j);
			}
		}
	}
return;
}
int main()
{   
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for(int i = 0; i < m ; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        nodes[i].dd = a, nodes[i].xx = b;
    }
    sort(nodes,nodes+m,cmp);
    for(int i = 0; i < m; i++)
    {
        add(nodes[i].dd,nodes[i].xx);
    }
    dfs(1);
    for(int i = 0; i < cnt; i++)
    cout << res[i] << " ";
    cout << endl;
    bfs();
    for(int i = 0; i < cnt1; i++)
    cout << res1[i] << " ";
    return 0;
}