#include <bits/stdc++.h>

using namespace std;

int main()
{
    //ifstream cin("in.txt");
    int n;
    cin >> n;
    int m;
    cin >> m;
    int k;
    cin >> k;
    vector<vector<int>> liszt(n + 1);
    for(int i = 1; i <= m; i++){
        int ferenc1;
        cin >> ferenc1;
        int ferenc2;
        cin >> ferenc2;

        liszt[ferenc1].push_back(ferenc2);
        liszt[ferenc2].push_back(ferenc1);
    }

    /*
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < liszt[i].size(); j++){
            cout << liszt[i][j] << " ";
        }
        cout << '\n';
    }
    */



    vector<int> d(n + 1);
    queue<int> q;
    q.push(k);

    while(!q.empty()){
        int a;
        a = q.front();
        q.pop();
        for(int i = 0; i < liszt[a].size(); i++){
            if(d[liszt[a][i]] == 0 && liszt[a][i]!=k){
                cout<<a<<" "<<liszt[a][i]<<'\n';
                d[liszt[a][i]] = d[a] + 1;
                q.push(liszt[a][i]);
            }
            else if(d[liszt[a][i]] >= d[a]+1){
                cout<<a<<" "<<liszt[a][i]<<'\n';
            }

        }
    }






    return 0;
}