rt

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n, m, x, y, f[MAXN];
vector < int > v[MAXN];
queue < int > Q;
void dfs(int x)
{
	cout << x << ' ';
	for (int i = 0; i < v[x].size(); i++)
	{
		if (f[v[x][i]] == 0)
		{
			f[v[x][i]] = 1;
			dfs(v[x][i]);
		}
	}
}
void bfs(void)
{
	while (!Q.empty())
	{
		int x = Q.front();
		Q.pop();
		cout << x << ' ';
		for (int i = 0; i < v[x].size(); i++)
		{
			if (f[v[x][i]] == 0)
			{
				f[v[x][i]] = 1;
				Q.push(v[x][i]);
			}
		}
	}
} 
int main(void)
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y;
		v[x].push_back(y);
	}
	f[1] = 1;
	dfs(1);
	cout << endl;
	memset(f, 0, sizeof(f));
	f[1] = 1;
	Q.push(1);
	bfs(); 
	return 0;
}