#include<bits/stdc++.h>
using namespace std;
vector<int> a[100001];
bool vis1[100001],vis2[100001];

void dfs(int x){
	vis1[x]=1;
	cout<<x<<" ";
	for(int i=0;i<a[x].size();i++){
		int is=a[x][i];
		if(vis1[is]==0)
		dfs(is);
	}
}
void bfs(int x){
	queue<int> q;
	q.push(x);
	cout<<x<<" ";
	vis2[x]=1;
	while(!q.empty()){
		int fro=q.front();
		for(int i=0;i<a[fro].size();i++){
			if(!vis2[a[fro][i]]){
				q.push(a[fro][i]);
				cout<<a[fro][i]<<" ";
				vis2[a[fro][i]]=1;
			}
		}
		q.pop();
	}
}
int main(){
	int n,m,u,v;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>u>>v;
		a[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
	sort(a[n].begin(),a[n].end());
	dfs(1);
	cout<<endl;
	bfs(1);
	return 0;
}

在dev里输入样例答案一样，但是在洛谷里一个没对