#include<iostream>
#include<vector>
#include<set>
#include<string>
#include<cstring>
using namespace std;
set<int> refers[101000];//记录每一个文献的后继
int n,m;
bool vis[101000]={0};
basic_string<int> dfs(int ind=1){
	vis[ind]=1;//标记
	basic_string<int> result{ind};//结果，basic_string支持拼接操作
	for(auto i:refers[ind])
		!vis[i]&&(result+=dfs(i),1);//继续搜索，遍历到的后继一定是存在的
	return result;
}
basic_string<int> bfs(int ind=1){
	memset(vis,0,sizeof(vis));
	basic_string<int> result{ind};
	vis[ind]=1;
	int now_ptr=0;
	while(now_ptr!=result.size()){
		for(auto i:refers[result[now_ptr]])
			!vis[i]&&(result.push_back(i),vis[i]=1);//保存&&标记
		now_ptr++;
	}
	return result;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		refers[x].insert(y);
	}
	basic_string<int> dfs_result=dfs(),bfs_result=bfs();
	for(auto i:dfs_result)
		cout<<i<<" ";
	cout<<endl;
	for(auto i:bfs_result)
		cout<<i<<" ";
}

2.85s，求大佬优化