#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,i,j,m;
bool vis[100005],vis2[100005];
vector<ll>v[100001];
void bfs(){
	queue<ll>q;
	q.push(1);
	vis[1]=1;
	while (!q.empty()){
		int cur=q.front();
		q.pop();
		cout<<cur<<' ';
		for (int i=0;i<v[cur].size();i++)
			if (!vis[v[cur][i]]){
				vis[v[cur][i]]=1;
				q.push(v[cur][i]);
			}
	}
}
void dfs(ll u){
    cout<<u<<' ';
	for (int i=0;i<v[u].size();i++)
		if (!vis2[v[u][i]]){
			vis2[v[u][i]]=1;
			dfs(v[u][i]);
		}
}
int main(){
    //freopen("find_literature.in","r",stdin);
    //freopen("find_literature.out","w",stdout);
	cin>>n>>m;
    while (m--){
        cin>>i>>j;
        v[i].push_back(j);
    }
    for (int i=1;i<=n;i++) sort(v[i].begin(),v[i].end());
	dfs(1);
	cout<<'\n';
	bfs();
}