#include<bits/stdc++.h>
using namespace std;
#define ft first
#define sd second
typedef long long ll;
typedef vector<bool> veb;
typedef vector<ll> vel;
typedef vector<vel> vevel;
typedef vector<vevel> vevevel;
typedef vector<pair<ll,ll>> velp;
typedef vector<pair<bool,bool>> velb;
typedef vector<char> vec;
typedef map<ll,ll> mll;
typedef map<char,ll> mcl;
typedef map<ll,char> mlc;
typedef map<ll,bool> mlb;
typedef map<char,char> mcc;
typedef vector<pair<char,char>> vecp;
typedef priority_queue<ll,vector<ll>,greater<>> pql;
typedef vector<pql> vpql;
typedef vector<queue<ll>> vql;
const ll mo = 1e9+7;
vql v;
veb b;
void dfs(ll x){
    cout<<x<<" ";
    b[x]=true;
    int s=v[x].size();
    while(s--){
        if(!b[v[x].front()]){
            dfs(v[x].front());
        }
        v[x].push(v[x].front());
        v[x].pop();
    }
}
void bfs(){
    pql q;
    q.push(1);
    while(!q.empty()){
        ll qf=q.top();
        cout<<qf<<" ";
        q.pop();
        int s=v[qf].size();
        while(s--){
            if(!b[v[qf].front()]){
                q.push(v[qf].front());
                b[v[qf].front()]=true;
            }
            v[qf].push(v[qf].front());
            v[qf].pop();
        }
    }
}
void slv(){
    int n,m;
    cin>>n>>m;
    b=veb(n+1);
    v=vql(n+1);
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        v[x].push(y);
        v[y].push(x);
    }
    b[1]=true;
    dfs(1);
    b=veb(n+1);
    for(int i=1;i<=n;i++){
        pql q;
        while(!v[i].empty()){
            q.push(v[i].front());
            v[i].pop();
        }
        while(!q.empty()){
            v[i].push(q.top());
            q.pop();
        }
    }
    cout<<"\n";
    b[1]=true;
    bfs();
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll t=1;
//    cin>>t;
    while(t--){
        slv();
    }
    return 0;
}