#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";
}