#include <iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>

using namespace std;

vector <vector <int>> v;
vector<bool> vis;
queue<int> q;
int a;
void DFS(int n)
{
    for(int i=0;i<v[n].size();i++)
    {
        if(vis[v[n][i]]==0)
        {
            vis[v[n][i]]=1;
            cout<<v[n][i]<<' ';
            DFS(v[n][i]);
        }
    }
}
void BFS(int n)
{
    while(q.empty()!=1)
        {
            cout<<q.front()<<' ';
            for(int i=0;i<v[q.front()].size();i++)
            {
                if(vis[v[q.front()][i]]==0)
                {
                    vis[v[q.front()][i]]=1;
                    q.push(v[q.front()][i]);
                }
            }
            q.pop();
        }
}
int main() {
    int b,c,x,y;
    cin>>a>>b>>c;
    v.resize(b);
    vis.resize(b);
    for(int i=0;i<b;i++)
    {
       cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=0;i<b;i++)
    {
        sort(v[i].begin(),v[i].end());
    }
    vis[c]=1;
    cout<<c<<' ';
    DFS(c);
        cout<<endl;
    vis.clear();
    vis.resize(b);
    vis[c]=1;
    q.push(c);
    BFS(c);
}