我们的工程师设计了一个通信网络，该网络由节点以及某些节点对之间的单向直接通信通道（边）组成。我们称如果存在一个由不同节点组成的序列 $p_1, p_2, \dots, p_k$，其中 $p = p_1$ 且 $q = p_k$，使得对于每个 $i = 1, \dots, k-1$ 都存在一条从 $p_i$ 发送数据到 $p_{i+1}$ 的边，则称节点 $q$ 可以从节点 $p$ 通过一条路径到达。该网络有一个中心节点 $r$，使得任何其他节点 $p$ 都可以从 $r$ 通过一条路径到达，并且对于任意一对节点 $p$ 和 $q$，至多存在一条路径可以从 $p$ 到达 $q$。

维护人员计划对网络进行改进，但尚未决定如何改进。他们正在考虑的一个想法是重新指定中心节点，因此他们想知道对于每个节点，有多少个节点可以从它通过一条路径到达。另一个想法是直接将网络去中心化，因此他们还想知道如何引入新的边，使得对于任意一对节点 $p$ 和 $q$，从 $p$ 到达 $q$ 恰好存在一条路径，反之亦然（即从 $q$ 到达 $p$ 也恰好存在一条路径）。

任务

你需要编写一个程序，计算每个节点可达的节点数量（子任务 A），并计算最少需要添加多少条新边，才能使任意节点到其他任意节点都以唯一的方式双向可达。你的程序还必须给出这些新边的列表（子任务 B）。

输入格式

输入的第一行包含三个整数 $N$（$1 \le N \le 100\,000$）表示节点数，$M$（$1 \le M \le 500\,000$）表示边数，以及 $r$（$1 \le r \le N$）表示中心节点。节点编号为 $1$ 到 $N$。

接下来的 $M$ 行包含边的描述。每行包含两个由空格分隔的整数 $p$ 和 $q$，对应一条可以从 $p$ 传输数据到 $q$ 的边。

输出格式

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

其余行包含子任务 B 的解： 输出的第二行包含一个整数 $K$，表示达到上述网络性质所需的最少新边数。 接下来的 $K$ 行列出这些新边：每行包含两个由空格分隔的整数 $u$ 和 $v$，对应一条从节点 $u$ 传输数据到 $v$ 的新边。

如果存在多个解，你的程序只需输出其中任意一个即可。

样例

输入样例 1

11 12 3
3 2
2 1
2 4
4 5
4 6
6 2
6 7
3 8
8 9
9 10
9 11
10 8

输出样例 1

1 6 11 6 1 6 1 4 4 4 1
5
1 3
5 4
7 6
11 9
8 3

子任务

在 50% 的测试数据中，$N$ 最多为 $10\,000$。

子任务 A 占 40% 的分数，子任务 B 占其余 60% 的分数。

如果你只解决子任务 B，你仍必须在第一行输出 $N$ 个整数（可以是任意值）。