#include<bits/stdc++.h>
using namespace std;
int n,m;
const int Max=10001;
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;
}

P5318