// P5318
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 数组模拟链式前向星
const int mxV = 1e5 + 1, mxE = 1e6 + 1;
struct E
{
	int v, next;
} e[mxE];
int head[mxV], cnt = 0;

// 加边
inline void add(int u, int v)
{
	cnt++;
	e[cnt].v = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}

// dfs
bool vis[mxV];
void dfs(int nd)
{
	cout << nd << " "; // 搜到点就输出
	vector<int> tmp; // 排列容器
  // 遍历
	for (int i = head[nd]; i; i = e[i].next)
	{
      // 未搜到的点加入排列容器
		if (!vis[e[i].v])
		{
			vis[e[i].v] = true;
			tmp.push_back(e[i].v);
		}
	}
  // 从小到大排列
	sort(tmp.begin(), tmp.begin() + tmp.size());
  // 按顺序下潜深搜
	for (int i = 0; i < tmp.size(); ++i)
	{
		dfs(tmp[i]);
	}
}

// bfs
// 数组模拟队列
int que[mxV], q1 = 0, q2 = -1;
void bfs(int nd)
{
  // 遇点输出
	cout << nd << " ";
	vector<int> tmp; // 排列容器
  // 遍历
	for (int i = head[nd]; i; i = e[i].next)
	{
      // 符合的点加入排列容器
		if (!vis[e[i].v])
		{
			tmp.push_back(e[i].v);
          // 并且标记已搜索
			vis[e[i].v] = true;
		}
	}
  // 从小到大排序
	sort(tmp.begin(), tmp.begin() + tmp.size());
  // 按顺序入队
	for (int i = 0; i < tmp.size(); ++i)
	{
		q2++;
		que[q2] = tmp[i];
	}
  // 按照顺序广搜
	while (q1 <= q2)
	{
		q1++;
		bfs(que[q1 - 1]);
	}
  // 每次搜到后继点都入队了而非直接输出，所有上面会在点输出前提前打好“已搜”标记，防止重复
}

int n, m;
int x, y;

int main()
{
  // 无优化输入
	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		cin >> x >> y;
		add(x, y);
	}
  // 提前定好起点，深搜广搜，因为共用vis[]所以有线性复杂度的重置
	vis[1] = true;
	dfs(1);
	cout << endl;
	for (int i = 1; i <= n; ++i)
	{
		vis[i] = false;
	}
	vis[1] = true;
	bfs(1);	
	return 0;
}