#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> pql;
const ll mo = 1e9+7;
vevel v;
veb b;
void dfs(ll x){
    cout<<x<<" ";
    b[x]=true;
    for(auto i:v[x]){
        if(!b[i]){
            dfs(i);
        }
    }
}
void bfs(){
    queue<ll> q;
    q.push(1);
    while(!q.empty()){
        ll qf=q.front();
        cout<<qf<<" ";
        q.pop();
        for(auto i:v[qf]){
            if(!b[i]){
                q.push(i);
                b[i]=true;
            }
        }
    }
}
void slv(){
    int n,m;
    cin>>n>>m;
    b=veb(n+1);
    v=vevel(n+1);
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    b[1]=true;
    dfs(1);
    b=veb(n+1);
    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;
}