#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <set>

using namespace std;

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<int, int> pii;

const int MAXN = 1e5 + 1e3;
const int MAXM = 5e5 + 1e3;

struct Edge { int to, ne; } es[MAXM], rves[MAXM];
int ecnt;
int firs[MAXN];
int rfirs[MAXN];

bool was[MAXN];

int ord[MAXN];
int oend;

void dfs(int v) {
  if (was[v]) return;
  was[v] = true;
  for (int i = firs[v]; i >= 0; i = es[i].ne)
    dfs(es[i].to);
  ord[oend++] = v;
}

int cols[MAXN];
int ccol;
int colsz[MAXN];
int collast[MAXN];

void dfs2(int v) {
  if (was[v]) return;
  was[v] = true;
  cols[v] = ccol; collast[ccol] = v;
  colsz[ccol]++;
  for (int i = rfirs[v]; i >= 0; i = rves[i].ne)
    dfs2(rves[i].to);
}

Edge tes[MAXN];
pii tes2[MAXN];
int tfirs[MAXN];
int tecnt;

int colsubsz[MAXN];
pii colpath[MAXN];

void dfs3(int v) {
  colsubsz[v] = colsz[v];
  colpath[v] = mp(0, -1);
  for (int i = tfirs[v]; i >= 0; i = tes[i].ne) {
    int b = tes[i].to;
    dfs3(b);
    colpath[v] = max(colpath[v], mp(1 + colpath[b].first, b));
    colsubsz[v] += colsubsz[b];
  }
}

pii ans[MAXN];
int alen;

void dfs4(int v, int locroot) {
  was[v] = true;
  int deg = 0;
  for (int i = firs[v]; i >= 0; i = es[i].ne) {
    int b = es[i].to;
    if (cols[b] == cols[v]) continue;
    if (was[b]) continue;

    dfs4(b, deg == 0 ? locroot : v);
    deg++;
  }
  if (v != locroot && deg == 0)
    ans[alen++] = mp(v, locroot);
}

int main() {
  #ifdef DEBUG
  freopen("std.in", "r", stdin);
  freopen("std.out", "w", stdout);
  #endif

  int n, m, root;
  while (scanf("%d%d%d", &n, &m, &root) >= 1) {
    root--;
    memset(firs, -1, sizeof(firs[0]) * n);
    memset(rfirs, -1, sizeof(rfirs[0]) * n);
    ecnt = 0;

    for (int i = 0; i < m; i++) {
      int a, b;
      scanf("%d%d", &a, &b), a--, b--;

      es[ecnt].to = b;
      es[ecnt].ne = firs[a];
      firs[a] = ecnt;

      rves[ecnt].to = a;
      rves[ecnt].ne = rfirs[b];
      rfirs[b] = ecnt;

      ecnt++;
    }

    oend = 0;
    memset(was, 0, sizeof(was[0]) * n);
    dfs(root);
    assert(oend == n);

    memset(was, 0, sizeof(was[0]) * n);
    memset(cols, -1, sizeof(cols[0]) * n);
    ccol = 0;
    for (int i = oend - 1; i >= 0; i--) {
      int v = ord[i];
      if (was[v]) continue;

      colsz[ccol] = 0;
      dfs2(v);
      ccol++;
    }
    int rcol = cols[root];

    memset(tfirs, -1, sizeof(tfirs[0]) * ccol);
    tecnt = 0;
    for (int a = 0; a < n; a++)
    for (int i = firs[a]; i >= 0; i = es[i].ne) {
      int b = es[i].to;
      if (cols[a] == cols[b]) continue;

      assert(tecnt < ccol - 1);
      tes[tecnt].to = cols[b];
      tes[tecnt].ne = tfirs[cols[a]];
      tes2[tecnt] = mp(a, b);
      tfirs[cols[a]] = tecnt++;
    }
    assert(tecnt == ccol - 1);

    dfs3(rcol);
    for (int i = 0; i < n; i++)
      printf("%d%c", colsubsz[cols[i]], "\n "[i + 1 < n]);

    alen = 0;
    memset(was, 0, sizeof(was[0]) * n);
    for (int i = n - 1; i >= 0; i--) {
      int v = ord[i];
      if (!was[v])
        dfs4(v, v);
    }

    printf("%d\n", alen);
    for (int i = 0; i < alen; i++)
      printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
  }
  return 0;
}