#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <stack>
#define MAXN 100005
using namespace std;

int N,M,R,t1,t2,L,LABEL[MAXN],SIZE[MAXN],S[MAXN],ai,INDEG[MAXN];
vector <int> G[MAXN],T[MAXN];
vector <pair<int,int> > ans;
bool visit[MAXN];

void flood(int x){
  visit[x] = 1;
  for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it)
    if(!visit[*it]) flood(*it);
  S[ai++] = x;
  G[x].clear();
}

void kosa(int x){
  visit[x] = 1;
  LABEL[x] = L;
  ++SIZE[L];
  for(vector<int>::iterator it=T[x].begin();it!=T[x].end();++it)
    if(!visit[*it]) kosa(*it);
}

void link(int x){
  S[ai++] = x;
  for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it)
    link(*it);
  if(G[x].size() == 0 && S[t1] != x){
    ans.push_back(pair<int,int>(x,S[t1]));
    t1 = ai-1;
  }
  --ai;
  if(t1 >= ai-1) t1 = ai-1;
}

void dfs(int x){
  for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it){
    dfs(*it);
    SIZE[x] += SIZE[*it];
  }
}

int main(){
  scanf("%d%d%d",&N,&M,&R);
  for(int i=0;i<M;++i){
    scanf("%d%d",&t1,&t2);
    G[t1].push_back(t2);
    T[t2].push_back(t1);
  }
  flood(R);
  memset(visit,0,sizeof(visit));
  while(ai){
    t1 = S[--ai];
    if(!visit[t1]){
      ++L;
      kosa(t1);
    }
  }
  for(int i=1;i<=N;++i){
    for(vector<int>::iterator it=T[i].begin();it!=T[i].end();++it)
      if(LABEL[i] != LABEL[*it]){
        G[*it].push_back(i);
        ++INDEG[i];
      }
  }
  for(int i=1;i<=N;++i) if(INDEG[i] == 0) ai = t1 = 0, link(i);
  for(int i=1;i<=N;++i) G[i].clear();
  for(int i=1;i<=N;++i){
    for(vector<int>::iterator it=T[i].begin();it!=T[i].end();++it)
      if(LABEL[i] != LABEL[*it])
        G[LABEL[*it]].push_back(LABEL[i]);
  }
  t1 = 0;
  dfs(LABEL[R]);
  for(int i=1;i<=N;++i) printf("%d ",SIZE[LABEL[i]]); printf("\n");
  printf("%d\n",ans.size());
  for(vector<pair<int,int> >::iterator it=ans.begin();it!=ans.end();++it)
    printf("%d %d\n",it->first,it->second);
  //system("pause");
}