#include<bits/stdc++.h>
using namespace std;

int n,m,x,y;
vector<int> e[100005];
bool visited[100005];

void dfs(int num){
	visited[num]=true;
	cout<<num<<" ";
	for(int i=0;i<e[num].size();i++){
		if(!visited[e[num][i]])dfs(e[num][i]);
	}
}

void bfs(int num){
	queue<int> que;
	que.push(num);
	int ti;
	while(!que.empty()){
		ti=que.front();
		cout<<ti<<" ";
		for(int i=0;i<e[ti].size();i++){
			if(!visited[e[ti][i]]){
				visited[e[ti][i]]=true;
				que.push(e[ti][i]);
			}
		}
		que.pop();
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		e[x].push_back(y);
	}
	for(int i=1;i<=n;i++){
		sort(e[i].begin(),e[i].end());
	}
	memset(visited,false,sizeof(visited));
	dfs(1);
	cout<<endl;
	memset(visited,false,sizeof(visited));
	bfs(1);
}