#include <vector>
#include <queue>
#include <iostream>

using ll = long long;
using namespace std;

int main()
{
    ll i, a, b, N, M, K;
    vector<pair<ll, ll>> sol;

    cin >> N >> M >> K;

    vector<vector<ll>> cities(N + 1);

    for(i = 0; i < M; i++)
    {
        cin >> a >> b;

        cities[a].push_back(b);
        cities[b].push_back(a);
    }

    queue<pair<ll, ll>> q;
    q.push(make_pair(K, 1));

    vector<ll> sp(N + 1);

    sp[1] = -1;
    for(i = 2; i <= N; i++) sp[i] = 0;

    while(q.size())
    {
        pair<ll, ll> c = q.front();
        q.pop();

        for(auto x : cities[c.first])
        {
            if(sp[x])
            {
                if(c.second >= sp[x])
                    continue;
            }
            else
            {
                sp[x] = c.second + 1;
                q.push(make_pair(x, c.second + 1));
            }

            sol.push_back(make_pair(c.first, x));
        }
    }

    cout << sol.size() << endl;

    for(auto x : sol)
        cout << x.first << ' ' << x.second << endl;

    return 0;
}