#include<iostream>
#include<queue>
#include<set>
#include<cstring>
using namespace std;

const int maxn = 1e6 + 5;
struct Q
{
	int next, to;
}t[maxn << 1];

queue<int> q;  int head[maxn];  int cnt;
bool vis[maxn];

inline void add(int u, int v)
{
	t[++cnt].to = v;
	t[cnt].next = head[u];
	head[u] = cnt;
}

void dfs(int u, int fa)
{
	cout << u << " ";
	set<int> s;
	for (int i = head[u]; i; i = t[i].next)
	{
		if (!vis[t[i].to]) vis[t[i].to] = true, s.insert(t[i].to);
	}
	for (auto it = s.begin(); it != s.end(); it++)
	{
		dfs(*it, u);
	}
}

int main()
{
	int n, m;  cin >> n >> m;
	int x, y;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		add(x, y);
	}

	//dfs
	vis[1] = true;
	dfs(1, 0);
	cout << endl;
	memset(vis, false, sizeof(vis));

	//bfs
	vis[1] = true;
	q.push(1);
	cout << 1 << " ";
	set<int> s;
	while (!q.empty())
	{
		s.clear();
		for (int i = head[q.front()]; i; i = t[i].next)
		{
			if (!vis[t[i].to]) vis[t[i].to] = true, s.insert(t[i].to);
		}

		for (auto it = s.begin(); it != s.end(); it++)
		{
			cout << *it << " ";
			q.push(*it);
		}
		q.pop();
	}
	return 0;
}