Henry 和 Hetty 最近被 Piatra Neamț 的一家网络公司聘用。他们的第一个项目是创建一个新型路由器，即革命性的 Connect Ethernet Operating Interface 2016，它由以下部分组成：

• $N$ 个输入节点，编号从 $1$ 到 $N$；
• $N$ 个输出节点，编号从 $N+1$ 到 $2N$；
• $K$ 个内部节点，编号从 $2N+1$ 到 $2N+K$；
• $M$ 条连接不同节点对的单向直接连接。

如果满足以下条件，节点 $X$ 可以向节点 $Y$ 发送数据（因此 $Y$ 可以从 $X$ 接收数据）：

• $X = Y$，或者
• 存在一个节点 $Z$，使得 $X$ 可以向 $Z$ 发送数据，且存在从 $Z$ 到 $Y$ 的直接连接。

如果节点 $X$ 可以向节点 $Y$ 发送数据，且 $X \neq Y$，我们定义从 $X$ 到 $Y$ 的数据路径为一组直接连接 $\{(A_1, A_2), (A_2, A_3), \dots, (A_{L-1}, A_L)\}$，其中 $L \ge 2$，且 $A_1 = X$，$A_L = Y$。

路由器工作正常需满足：

• 每个输入节点都能向每个输出节点发送数据；
• 每个输入节点只能从自身接收数据；
• 每个输出节点只能向自身发送数据；
• 对于任意两个节点 $X$ 和 $Y$，如果 $X \neq Y$ 且 $X$ 可以向 $Y$ 发送数据，则 $Y$ 不能向 $X$ 发送数据；
• 对于任意两个节点 $X$ 和 $Y$，如果 $X \neq Y$ 且 $X$ 可以向 $Y$ 发送数据，则从 $X$ 到 $Y$ 的数据路径是唯一的。特别地，任意两个节点 $X$ 和 $Y$ 之间最多只能有一条直接连接。

像其他电子设备一样，路由器工作需要电力。定义操作节点 $X$ 所需的功率为 $P_X = IN_X \times OUT_X$，其中 $IN_X$ 是可以向 $X$ 发送数据的输入节点数量，$OUT_X$ 是可以从 $X$ 接收数据的输出节点数量。定义路由器的最大功率为 $P_{\max} = \max(P_1, P_2, \dots, P_{2N+K})$。

项目经理给 Henry 和 Hetty 提供了一些测试路由器的技术规格，如下表所示。对于每项规格，经理要求路由器：

• 恰好有 $N$ 个输入节点和 $N$ 个输出节点；
• 使用最多 $M_{\lim}$ 条直接连接；
• 使用的最大功率最多为 $P_{\lim}$；
• 总共使用最多 $500\,000$ 个节点（总节点数 $N_{\text{tot}} = 2N + K \le 500\,000$）。

对于他们成功构建的每个路由器，Henry 和 Hetty 将获得表中列出的相应分数。

输入格式

你不需要提交解决该任务的程序。相反，在从评分系统下载的压缩包中，你会找到文件 1-router.in, 2-router.in ... 7-router.in。这些文件是每个测试的输入数据。你可以使用命令 unzip router.zip 从压缩包中提取输入文件。

每个输入文件 1-router.in, 2-router.in ... 7-router.in 描述一个单独的测试。每个文件的第一行包含三个整数：$N$（输入和输出节点的数量）、$M_{\lim}$（允许的最大直接连接数）和 $P_{\lim}$（路由器使用的最大功率）。

输出格式

对于每个输入文件，你应该创建相应的输出文件 1-router.out, 2-router.out ... 7-router.out。将所有这些文件放在一个名为 router-out 的目录中，并创建一个包含该目录的 zip 压缩包。你可以使用命令 zip -r router-out.zip router-out 来创建压缩包 router-out.zip。你应该提交此压缩包作为解决方案。

在每个输出文件 1-router.out, 2-router.out ... 7-router.out 中，你需要输出两个由空格分隔的整数：$N_{\text{tot}} = 2N + K$（表示构建路由器所使用的节点总数）和 $M$（表示所使用的直接连接总数）。在接下来的 $M$ 行中，每一行应输出一对整数 $X$ 和 $Y$，表示构建了一条从节点 $X$ 到节点 $Y$ 的直接连接。

实现细节

在从评分系统下载的压缩包中，你还会找到两个脚本 gen-out.sh 和 check.sh，以及一个名为 verif_contestant 的可执行文件。如果你将这三个文件、输入文件以及一个名为 router 的可执行文件放在同一个目录下，你可以使用命令 bash gen-out.sh 为每个输入文件生成你的可执行文件产生的输出文件。然后，你可以使用命令 bash check.sh 来测试你的输出相对于任务和输入约束的正确性。可执行文件 router 应由你创建的源文件生成，该源文件从名为 router.in 的文件中读取输入数据，并将输出打印到名为 router.out 的文件中。

样例

输入 1

3 100 200

输出 1

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

说明 1

Henry 和 Hetty 必须构建一个具有 3 个输入节点和 3 个输出节点的路由器，该路由器最多使用 100 条直接连接，且最大功率为 200。

他们总共使用了 9 个节点（输入节点 1、2 和 3，输出节点 4、5 和 6，以及内部节点 7、8 和 9），以及 8 条直接连接。

该路由器使用的最大功率为 9，由顶点 8 的功率给出，它可以从 $IN_8=3$ 个输入节点接收数据，并可以向 $OUT_8=3$ 个输出节点发送数据。

输入 2

3 100 200

输出 2

6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6

说明 2

另一个满足相同规格的有效路由器总共使用了 6 个节点（3 个输入节点和 3 个输出节点）。

该路由器使用的最大功率为 3：每个输入节点只能从自身接收数据，并能向所有 3 个输出节点发送数据。同样，每个输出节点可以从所有 3 个输入节点接收数据，且只能向自身发送数据。