#include<bits/stdc++.h>
using namespace std;
vector<int>p[1000001];
queue <int> q; 
int vis[1000001];
void dfs(int d){
	cout<<d<<' ';
	for(int i=0;i<p[d].size();i++){
		if(!vis[p[d][i]]){
			vis[p[d][i]]=1;
			dfs(p[d][i]);
		}
	}
}
void bfs(int x){
	vis[x]=1;
	q.push(x);
	while(!q.empty()) {
		int v=q.front();
		q.pop();
		cout<<v<<" ";
		for(int i=0;i<p[v].size();i++) 
			if(!vis[p[v][i]]){
				vis[p[v][i]]=1;
				q.push(p[v][i]);
			}
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		p[a].push_back(b);
	}
    for(int i=1;i<=n;i++){
        sort(p[i].begin(),p[i].end());
}
	dfs(1);
	cout<<endl;
		for(int i=1;i<=1000001;i++){
		vis[i]=0;
	}
	bfs(1);
	return 0;
}

谢谢了