Cannot parse: undefinedms error parsing time

题目描述

译自 CEOI2016 Day2 T3「Router」

Henry 和 Hetty 最近被一家来自 Piatra Neamț 的网络公司聘用。他们的第一个任务是开发一个新款路由器：革命性的 连接以太网操作接口 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$ 到 $Y$ 的一条数据链路为一些直接连接的集合 $\{(A_1,A_2),(A_2,A_3),\ldots,(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=\text{IN}_X\times \text{OUT}_X$，其中 $\text{IN}_X$ 表示可以向 $X$ 发送数据的输入节点个数，$\text{OUT}_X$ 是可以从 $X$ 接收数据的输出节点个数。定义路由器使用能量的最大值为 P_\max=\max(P_1,P_2,\ldots, P_{2N+K})。

项目经理给了 Henry 和 Hetty 开发一些测试路由器的技术细节，如下表所示。对于每条限制，项目经理想要一个路由器，满足：

• 有恰好 $N$ 个输入节点和 $N$ 个输出节点；
• 使用最多 $M_{\text{lim}}$ 条直接连接；
• 使用最大能量至多是 $P_{\text{lim}}$；
• 最多总共用 $5\times 10^5$ 个节点（总节点数 $N_{\text{tot}}=2N+K\le 5\times 10^5$）

测试数据编号	$N$	$M_{\text{lim}}$	$P_{\text{lim}}$	得分
$1$	$118$	$10^6$	$10^6$	$4$
$2$	$223$			$5$
$3$	$1250$	$5\times 10^5$	$5\times 10^5$	$6$
$4$	$5101$
$5$	$9934$			$26$
$6$	$9955$		$10^5$	$30$
$7$	$9978$	$10^5$	$10^5$	$23$

对于每个他们成功开发的路由器，Henry 和 Hetty 会获得一些得分，如上表所示。

输入格式

你不应该提交解决上述问题的程序。你需要先从「文件-附加文件」中下载全部输入。输入文件名称为 1-router.in 到 7-router.in。

每个输入文件都描述了一组数据。每个文件均只包含一行三个整数 $N,M_{\text{lim}},P_{\text{lim}}$，意义如题目描述。

输出格式

对于每个输入文件，你需要建立对应的输出文件 1-router.out 到 7-router.out。你可以分别提交或打包提交，格式为 zip 格式。

对于每个输出文件，首先输出两个整数 $N_\text{tot}=2N+K$ 和 $M$，分别表示开发路由器使用的总节点数和使用的直接连接的数量。接下来 $M$ 行，对于每行你应该输出两个整数 $X,Y$，表示建立一条从 $X$ 到 $Y$ 的直接连接。

样例

对于输入：

3 100 200

第一组样例输出为：

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

在这组数据中，Henry 和 Hetty 必须开发一个有 $3$ 个输入和 $3$ 个输出节点的路由器，最多使用 $100$ 条直接连接，并且最大使用能量为 $200$。

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

路由器的最大使用能量是 $9$，是 $8$ 号节点会使用的。因为这个节点可以接收 $\text{IN}_8=3$ 个输入节点的数据，并且给 $\text{OUT}_8=3$ 个输出节点发送数据。

第二组样例输出为：

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

另一种相同限制下的合法的路由器设计需要使用 $6$ 个节点（三个输入节点和三个输出节点）。

这个路由器最大使用能量是 $3$：每个输入节点只可以从自己接收数据，并可以向所有三个输出节点发送数据。类似地，对于每个输出节点，可以从所有三个输入节点接收数据，并只能向自己发送数据。