#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int n, m;
int x, y;
struct Node
{
	int to, next;
} a[N];
int k ;
int pre[N];
int vis[N];
void add(int u, int v)
{
	a[++k] = {v, pre[u]};
	pre[u] = k;
}

void dfs(int x)
{
	printf("%d ", x);
	vis[x] = 1;
	vector<int> v;
	for (int i = pre[x]; i; i = a[i].next)
	{
		v.push_back(a[i].to);
	}
	sort(v.begin(),v.end());
	for(auto e:v)
	{
		int to = e;
		if (!vis[to])
		{
			dfs(to);
		}
	}
}

void bfs(int u)
{
	queue<int> q;
	vis[u]=1;
	q.push(u);
	while(!q.empty())
	{
		int k=q.front();
		q.pop();
		printf("%d ",k);
		vector<int> v;
		for(int i=pre[k]; i; i=a[i].next)
		{
			v.push_back(a[i].to);
		}
		sort(v.begin(),v.end());
		for(auto e:v)
		{
			int to=e;
			if(!vis[to])
			{
				q.push(to);
				vis[to]=1;
			}
		}
	}
}


int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &x, &y);
		add(x, y);
	}
	dfs(1);
	printf("\n");
	memset(vis,0,sizeof(vis));
	bfs(1);
	return 0;
}