#include<bits/stdc++.h>
#define maxn 1000000
using namespace std; 
int n,m;
vector<int>p[maxn];
queue<int>q;
bool b[maxn];
void dfs(int a) {
	cout<<a<<" ";
	for(int i=0,sz=p[a].size(); i<sz; i++) {
		if(!b[p[a][i]]) {
			b[p[a][i]]=true;
			dfs(p[a][i]);
		}
	}
}
void bfs(int a) {
	q.push(1);
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		for(int i=0,sz=p[x].size(); i<sz; i++) {
			if(!b[p[x][i]]) {
				b[p[x][i]]=true;
				q.push(p[x][i]);
			}

		}
		cout<<x<<' ';
	}
}
int main() {
	cin>>n>>m;
	for(int i=1; i<=m; i++) {
		int x,y;
		cin>>x>>y;
		p[x].push_back(y);

	}
	b[1]=true;
	bfs(1);
	cout<<endl;
	dfs(1);
	return 0;
}

各位神犇帮我看看，谢谢啦