2856 「CEOI2012」网络

译自 CEOI 2012 Day2 T3「Network」

我们的工程师设计了一个通信网络，它由节点和一些节点对之间的单向直接通信信道（链路）组成。如果有一系列不同的节点 $p_1, p_2, \dots, p_k$，且 $p = p_1, q = p_k$，我们说节点 $q$ 从节点 $p$ 在一条路径上是可达的。这样，对于每一个 $i = 1, \dots, k-1$，都有一个从 $p_i$ 到 $p_{i+1}$ 传输数据的链路。这个网络有一个中心节点 $r$，因此 $r$ 可以通过一条路径到达其他任何节点 $p$，对于任意一对节点 $p$ 和 $q$，从 $p$ 到达 $q$ 的路径最多只有一条。维护者计划对网络进行改进，但尚未决定如何改进。他们正在考虑的一个想法是重新分配中心节点，因此他们想知道对于每个节点，在一条路径上有多少节点是可达的。另一个想法是将网络去中心化，他们还想知道如何引入新的链路，从而使得对于任意一对节点 $p$ 和 $q$，只有一条路径可以从 $p$ 到达节点 $q$，反之亦然。

您将编写一个程序，计算每个节点（子任务 A）的可达节点的数量，并计算使每个节点以独特的方式从每个其他节点可达所需的最小新链路数量。你的程序也需要给出新链接的列表（子任务 B）。

输入的第一行包含三个整数：节点数 $N$，链路数 $M$，中心节点 $r$。节点的编号从 $1$ 到 $N$。

接下来 $M$ 行是链路的描述。每行包含两个整数 $p$ 和 $q$ 对应一条可以将数据从 $p$ 传输到 $q$ 的链路。

输出的第一行包含子任务 A 的解：$N$ 个以空格分隔的整数，其中第 $i$ 个数字是节点 $i$ 的可达节点数（包括 $i$ 本身）。

剩下的行包含子任务 B 的解：输出的第二行包含一个整数 $K$，这是实现上述网络属性所需的最小新链路数。接下来的 $K$ 行列出了新的链路：每一行包含两个整数 $u$ 和 $v$，用空格隔开，它们对应一个从节点 $u$ 传输数据到节点 $v$ 的新链路。

如果有多组解，输出任意一组即可。

对于 $50\%$ 的数据，$1 \leq N \leq 10000$；
对于 $100\%$ 的数据，$1 \leq N \leq 100000$，$1 \leq M \leq 500000$，$1 \leq r \leq N$。

子任务 A 占据了每个测试点 $40\%$ 的分数，子任务 B 占据了其余 $60\%$ 的分数。

如果你只想回答子任务 A，请在第二行输出 $0$ 后结束程序；
如果你只想回答子任务 B，也需要在第一行输出 $N$ 个任意整数。