network

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <cstdio>

using namespace std;

typedef long long ll;
typedef long double ld;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

const int maxn=100005;

int was[maxn];
int kanswer=-1;
int ans[maxn];
vector<int> gr1[maxn],gr2[maxn];
int ansc[maxn];
int beg[maxn],end[maxn];
int lcmp[maxn];
int ttime[maxn];
int comp[maxn];
int n,m,root,timer;
bool in[maxn];
int r[maxn];
int answer1[maxn],answer2[maxn];

void go1(int cur)
{
    if (was[cur]==1) return;
    was[cur]=1;
    for (int i=0;i<gr1[cur].size();i++) go1(gr1[cur][i]);
    ttime[++timer]=cur;
}

void go2(int cur,int cmp)
{
    if (was[cur]==1) return;
    was[cur]=1;
    for (int i=0;i<gr2[cur].size();i++) go2(gr2[cur][i],cmp);
    comp[cur]=cmp;
    lcmp[++end[cmp]]=cur;
}

int main()
{
    int startt=clock();
    scanf("%d%d%d",&n,&m,&root),root--;
    for (int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b),a--,b--;
        gr1[a].push_back(b);
        gr2[b].push_back(a);
    }
//  if (n<=10000) solveslow();
//  memset(was,0,sizeof(was));
    timer=-1;
    go1(root);
    memset(was,0,sizeof(was));
    int kv=0;
    end[0]=-1;
    for (int i=0;i<n;i++) if (was[ttime[n-i-1]]==0)
    {
        go2(ttime[n-i-1],kv++);
        end[kv]=end[kv-1];
        end[kv-1]++;
        beg[kv]=end[kv-1];
    }
//  memset(ansc,0,sizeof(ansc));
    for (int i=kv-1;i>=0;i--)
    {
        for (int u=beg[i];u<end[i];u++)
        {
            int v=lcmp[u];
            for (int j=0;j<gr1[v].size();j++) if (comp[gr1[v][j]]!=i)
            {
                ansc[i]+=ansc[comp[gr1[v][j]]];
            }
        }
        ansc[i]+=end[i]-beg[i];
    }
    for (int i=0;i<n;i++) ans[i]=ansc[comp[i]];
    for (int i=0;i<n;i++) printf("%d ",ans[i]);
    printf("\n");
    for (int i=kv-1;i>=0;i--)
    {
        for (int u=beg[i];u<end[i];u++)
        {
            int v=lcmp[u];
            for (int j=0;j<gr1[v].size();j++) if (comp[gr1[v][j]]!=i)
            {
                in[gr1[v][j]]=true;
            }
        }
    }
    in[root]=true;
    for (int i=0;i<n;i++) r[i]=i;
    for (int i=kv-1;i>=0;i--)
    {
        for (int u=beg[i];u<end[i];u++)
        {
            int v=lcmp[u];
            for (int j=0;j<gr1[v].size();j++) if (comp[gr1[v][j]]!=i)
            {
                if (in[v])
                {
                    if (r[v]==v) r[v]=r[gr1[v][j]];
                    else answer1[++kanswer]=r[gr1[v][j]],answer2[kanswer]=v;
                } else answer1[++kanswer]=r[gr1[v][j]],answer2[kanswer]=v;
            }
        }
    }
    if (r[root]!=root) answer1[++kanswer]=r[root],answer2[kanswer]=root;
    printf("%d\n",kanswer+1);
    for (int i=0;i<kanswer+1;i++) printf("%d %d\n",answer1[i]+1,answer2[i]+1);
    return 0;
}