#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <iomanip>
#include <vector>
#include <queue>
using namespace std;

int n,m;
vector<int> e[1000005];
bool vis[1000005];
void dfs(int x){
	cout<<x<<" ";
	vis[x]=true;
	for(int i=0;i<e[x].size();i++)
		if(!vis[e[x][i]])
			dfs(e[x][i]);
} 
void bfs(){
	memset(vis,0,sizeof vis);
	queue<int> q;
	q.push(1),vis[1]=true;
	while(!q.empty()){
		int f=q.front();
		q.pop();
		cout<<f<<" ";
		for(int i=0;i<e[f].size();i++)
			if(!vis[e[f][i]]){
				q.push(e[f][i]);
				vis[e[f][i]]=true;
			}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		e[u].push_back(v);
	}
	dfs(1),cout<<endl;
	bfs();
	return 0;
}

蒟蒻无力，求大佬指教