#include <bits/stdc++.h>
using namespace std;
int a[1005][1005];
int vis[1005];
int n,m;
void dfs(int cur){
vis[cur]=1;
cout << cur << ' ';
for(int i=1;i<=n;i++){
if(!vis[i] && a[cur][i]){
dfs(i);
}
}
}
void bfs(int cur){
queue<int> q;
q.push(cur);
vis[cur]=1;
cout << cur << ' ';
while(!q.empty()){
int head = q.front();
for(int i=1;i<=n;i++){
if(!vis[i] && a[head][i]){
vis[i]=1;
cout << i << ' ';
q.push(i);
}
q.pop();
}
}
}
int main(){
cin >> n >> m;
for(int i = 0;i < m;i++){
int x,y;
scanf("%d%d",&x,&y);
a[x][y] = 1;
}
dfs(1);
cout << '\n';
memset(vis,0,sizeof vis);
bfs(1);
}
