#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 +10;
vector<int> g[N];
queue<int> q;
int n,m,vis[N],dis[N];
void dfs(int x){
    vis[x]=1;
    cout<<x<<" ";
    for(int i=0;i<g[x].size();i++){
        int y=g[x][i];
        if(vis[y])continue;
        vis[y]=1;
        dfs(y);
    }
}
void bfs(int x){
    for(int i=0;i<n;i++)dis[i]=INT_MAX;
    q.push(x);
    dis[x]=0;
    while(!q.empty()){
        int u=q.front();
        cout<<u<<" ";
		q.pop();
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            if(dis[v]!=INT_MAX)continue;
            dis[v]=dis[u]+1;
            q.push(v);
        }
    }
}
int main(){
    cin>>n>>m;
    while(m--){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[u].push_back(u);
    }
    //sort(g,g+n);
    vis[1]=1;
    dfs(1);
    cout<<endl;
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    bfs(1);
    return 0;
}