#include<iostream>
#include<stack>
#include<string>
#include<map>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
int n,m;
const int N=1e5+10;
vector<int>a[N];
bool f[N];
void dfs(int k){
    cout<<k<<" ";
    vector<int>::iterator j;
    for(j=a[k].begin();j!=a[k].end();j++){
        if(!f[*j]){
            f[*j]=1;
            dfs(*j);
        }
    }
    return;
}
void bfs(int k){
    f[1]=1;
    queue<int>q;
    q.push(1);
    vector<int>::iterator j;
    while(!q.empty()){
        cout<<q.front()<<" ";
        for(j=a[q.front()].begin();j!=a[q.front()].end();j++){
            if(!f[*j]){
                f[*j]=1;
                q.push(*j);
            }
        }
        q.pop();
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        a[min(u,v)].push_back(max(u,v));
        
    }
    vector<int>::iterator j;
//    for(int i=1;i<=n;i++){
//        sort(a[i].begin(),a[i].end());
//        for(j=a[i].begin();j!=a[i].end();j++){
//            cout<<i<<"->"<<*j<<" ";
//        }
//        cout<<endl;
//    }
    f[1]=1;
    dfs(1);
    memset(f,0,sizeof(f));
    cout<<endl;
    bfs(1);
    return 0;
}