#include<iostream>
#include<queue>

#define VertexType int
#define InfoType int
#define MAX_VERTEX_NUM 100

using namespace std;
typedef struct {
	VertexType adj;
	InfoType* info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
	AdjMatrix arcs;
	VertexType vexs[MAX_VERTEX_NUM];
	int vexnum, arcnum;
}MGraph;
int visited_1[MAX_VERTEX_NUM], visited_2[MAX_VERTEX_NUM];

void build(MGraph* graph) {
	cin >> graph->vexnum >> graph->arcnum;

	for (int i = 1; i <= graph->vexnum; i++) {
		for (int j = 1; j <= graph->vexnum; j++) {
			graph->arcs[i][j].adj = 0;
			graph->arcs[i][j].info = NULL;
		}
	}

	for (int i = 1; i <= graph->arcnum; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;
		graph->arcs[temp1][temp2].adj = 1;
	}
}

void DFS(MGraph* graph, int vertex) {
	visited_1[vertex] = 1;
	cout << vertex << " ";
	for (int i = 1; i <= graph->vexnum; i++) {
		if (graph->arcs[vertex][i].adj == 1 && !visited_1[i])
			DFS(graph, i);
	}
}

void BFS(MGraph* graph, int vertex) {
	queue<int> Q;
	Q.push(vertex);
	visited_2[vertex] = 1;
	cout << vertex << " ";

	while (!Q.empty()) {
		int fro = Q.front();
		for (int i = 1; i <= graph->vexnum; i++) {
			int point = graph->arcs[fro][i].adj;
			if (point && !visited_2[i]) {
				Q.push(i);
				cout << i << " ";
				visited_2[i] = 1;
			}
		}
		Q.pop();
	}
}

int main(void) {
	MGraph graph;
	build(&graph);
	DFS(&graph, 1);
	cout << endl;
	BFS(&graph, 1);
	return 0;
}