#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>

typedef int Vertex;
typedef std::vector<std::vector<Vertex>> LGraph;
typedef LGraph* ptrLGraph;

const int maxn = 1e5+5;
LGraph G;
Vertex visited[maxn]{0};
std::queue<Vertex> Q;

void dfs(Vertex G);
void bfs(Vertex G);

int main(void) {

	int n,m;
	std::cin >> n >> m;
	G.resize(n+1);
	//建立这个图
	for (int i = 1; i <= m; i++) {
		Vertex x, y;
		std::cin >> x >> y;
		G[x].push_back(y);
	}
	for (int i = 1; i <= n; i++)
		sort(G[i].begin(), G[i].end());
	visited[1] = true;
	dfs(1);
	std::cout << std::endl;
	memset(visited, 0, sizeof(visited));
	visited[1] = true;
	bfs(1);

	return 0;
}

void dfs(Vertex x) {
	std::cout << x << " ";
	for (int i=0; i < G[x].size(); i++) 
		if (!visited[G[x][i]]) {
			visited[G[x][i]] = true;
			dfs(G[x][i]);
		}
}

void bfs(Vertex x) {
	Q.push(x);
	while (!Q.empty()) {
		Vertex v = Q.front();
		std::cout << v << " ";
		Q.pop();
		for(int i=0;i<G[v].size();i++)
			if (!visited[G[v][i]]) {
				visited[G[v][i]] = true;
				Q.push(G[v][i]);
			}
	}
}