#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m, fo;
    cin >> n >> m >> fo;
    
    vector<vector<int>> graph(n);
    
    for (int i = 0; m > i; i++) {
        int a, b;
        cin >> a >> b;
        
        a--;
        b--;
        
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    vector<int> voltam(n, -1);
    // honnan, hova
    queue<pair<int, pair<int, int>>> sor;
    
    vector<pair<int, int>> felujit;
    
    sor.push({0, {fo-1, 0}});
    
    while (!sor.empty()) {
        auto current = sor.front();
        sor.pop();
        
        int honnan = current.first;
        int hova = current.second.first;
        int counter = current.second.second;
        
        if (voltam[hova] < counter && voltam[hova] != -1) continue;
        
        felujit.push_back({honnan, hova});
        
        if (voltam[hova] != counter) {
            for (int szom : graph[hova]) {
                sor.push({hova, {szom, counter+1}});
            }
        }
        
        voltam[hova] = counter;
    }
    
    cout << felujit.size()-1 << endl;
    
    for (int i = 1; felujit.size() > i; i++) {
        cout << felujit[i].first+1 << " " << felujit[i].second+1 << endl;
    }

    return 0;
}