#include <iostream>
//#include <fstream>
#include <vector>
#include <deque>
#include <queue>
#include <climits>

#define ll long long 

using namespace std;
//ifstream cin ("input.in");
//ofstream cout ("output.out");

ll n,m,i,j,a,b,start;
struct element
{
    bool seen;
    ll step=LLONG_MAX,from=-1;
    vector <ll> sz;
};


vector <pair<ll,ll> > res;

struct road
{
    ll where,steps,from;
};

priority_queue<road> que;
bool operator< (const road& a, const road& b)
{
    return a.steps>b.steps;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin>>n>>m>>start;
    vector <element> x(n+1);
    deque<pair<ll,ll> >v;
    for (i=1;i<=m;++i)
    {
        cin>>a>>b;
        x[a].sz.push_back(b);
        x[b].sz.push_back(a);
    }

    x[start].step=0;
    que.push({start,0,0});
    //v.push_back(start);
    //x[start].seen=true;
    ll db=0;
    road curr;
    while (!que.empty())
    {
        curr=que.top();
        while (x[curr.where].seen&&!que.empty())
        {
            que.pop();
            if (!que.empty()) curr=que.top();
        }

        if (que.empty()) break;
       //db++;
        x[curr.where].seen=true;
        x[curr.where].step=curr.steps;
        x[curr.where].from=curr.from;
        //res.push_back({curr.where,curr.from});
        for (auto &e:x[curr.where].sz)
        {
            if (curr.steps+1<x[e].step)
            {
                x[e].step=curr.steps+1;
                que.push({e,curr.steps+1,curr.where});
            }
        }
    }

    v.push_back({start,0});
    pair<ll,ll> r;
    for (i=1;i<=n;++i) x[i].seen=false;
    x[start].seen=true;
    while (!v.empty())
    {
        r=v[0];
        v.pop_front();

        for (auto& e:x[r.first].sz)
        {
            if (x[e].step==r.second+1)
            {
                res.push_back({e,r.first});
                if (!x[e].seen)
                {
                    x[e].seen=true;
                    v.push_back({e,x[e].step});
                }
            }
        }
    }

    cout<<res.size()<<"\n";
    for (auto&e:res) cout<<e.first<<" "<<e.second<<"\n";
}