#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v[1000];
vector<bool> check(1000);
queue<int> qu;
vector<int> find;
int n,m,start;
void dfs(int present)
{
    if(check[present]==false)
    {
        check[present]=true;
        cout<<present<<" ";
        for(int i=0; i<v[present].size(); i++)
        {
            if(check[v[present][i]]==false)
                dfs(v[present][i]);
        }
    }
    else
    {
        return;
    }
}
int main() {
    cin>>n>>m>>start;
    for(int i=0; i<m; i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=0; i<n; i++)
    {
        sort(v[i].begin(), v[i].end());
    }
    for(int i=1; i<=n; i++)
    {
        check[i]=false;
    }
    dfs(start);



    cout<<endl;


    //bfs
    for(int i=1; i<=n; i++)
    {
        check[i]=false;
    }
    qu.push(start);
    cout<<start<<" ";
    check[qu.front()]=true;
    while(!qu.empty())
    {
        for(int i=0; i<v[qu.front()].size(); i++)
        {
            if(check[v[qu.front()][i]]==false)
            {
                qu.push(v[qu.front()][i]);
                cout<<v[qu.front()][i]<<" ";
                check[v[qu.front()][i]]=true;
            }
        }
        qu.pop();
    }
    cout<<endl;
}
//탐색알고리즘
//그래프[DFS,BFS] - 노드, 엣지(간선)
//vector<int> v[5]; - 가진 노드수 만큼 만들어놓기
//인접 리스트와 인접행렬의 개념