P13855 [CERC 2023] Keys

Alice 和 Bob 住在一座巨大的豪宅里，这座豪宅有 $n$ 个房间（其中一个代表室外，他们会在那里玩月亮游戏），以及 $m$ 扇连接房间的门。每一扇门连接两个房间，或者一个房间与室外，并且每一扇门都有一把唯一的钥匙，仅能打开这扇门。每一扇门在你通过后都会自动关闭并上锁，因此想要通过一扇门总是需要相应的钥匙。豪宅很大，但 Alice 和 Bob 实际上只用一个房间——他们的卧室。其他房间只是为了让房子看起来更大，从而让邻居们嫉妒。 这种奇怪的房屋设计如今给 Alice 和 Bob 带来了麻烦。Bob 要外出旅行两周。一周后，Alice 也要出国一个月，而当她离开时，她需要合适的钥匙才能离开房子。然而，Bob 回来时也需要钥匙才能进屋，因为 Alice 那时已经不在家帮他开门。现在 Alice 和 Bob 需要想办法分配钥匙，使得 Alice 能从房间 $0$（他们的卧室）到达 $1$（室外），而 Bob 能在一周后从房间 $1$（室外）回到 $0$（卧室）。 幸运的是，Alice 想起她在外出时可以把一些钥匙留在途中，这样 Bob 回来时就能捡到并继续使用。这样，他们就可以共享通过相同的门。当然，她不能把钥匙丢在房间 $1$（室外），因为邻居可能会捡到并闯进他们的家。 你能帮 Alice 和 Bob 分配钥匙，并规划他们在豪宅中的行程吗？ ### 任务 你将得到 Alice 和 Bob 的豪宅的描述：$m$ 扇门连接着 $n$ 个房间，这些房间编号为 $0$ 到 $n-1$，其中 $1$ 是室外，$0$ 是卧室。第 $i$ 扇门需要钥匙编号 $i$（从 $0$ 开始计数）才能打开。 你需要先输出两行，分别表示 Alice 和 Bob 拥有的钥匙编号，编号之间用空格隔开。他们可以不使用所有钥匙，但不允许两人同时拥有同一把钥匙（也不允许某人拥有多份同一把钥匙）。 然后，你需要输出 Alice 和 Bob 将要遵循的指令。首先，输出 Alice 从房间 $0$ 到 $1$ 的移动过程，指令格式有两种： - `"MOVE x"` 表示移动到房间 $x$（假设 Alice 当前所在的房间与 $x$ 之间有门，且 Alice 持有该门的钥匙）， - `"DROP k_1 k_2 …"` 表示在当前房间丢下钥匙 $k_1, k_2, …$（钥匙编号以空格隔开）。这意味着 Alice 不再携带这些钥匙。 当 Alice 完成移动后，输出一行 `"DONE"`。Alice 应当最终停在房间 $1$。在遵循指令的过程中，Alice 可以多次经过房间 $0$ 或 $1$。 接着，输出 Bob 从房间 $1$ 到 $0$ 的移动过程，指令格式也有两种： - `"MOVE $x$"` 表示移动到房间 $x$（假设 Bob 当前所在的房间与 $x$ 之间有门，且 Bob 持有该门的钥匙）， - `"GRAB"` 表示捡起当前房间的所有钥匙。Bob 总是一次性捡起 Alice 在该房间留下的所有钥匙。如果没有钥匙，则什么也不会捡。 当 Bob 完成移动后，输出一行 `"DONE"`。Bob 应当最终停在房间 $0$。在遵循指令的过程中，Bob 可以多次经过房间 $0$ 或 $1$。 备注：允许（虽然没什么用）在没有钥匙的房间执行 `"DROP"` 空钥匙列表，或者在没有钥匙的房间执行 `"GRAB"`，甚至在房间 $1$（即室外）执行 `"GRAB"`。

第一行包含两个整数 $n$ 和 $m$，分别表示房间数（包括室外）和门的数量。接下来有 $m$ 行，每行描述一扇门。第 $i$ 行（从 $0$ 开始计数）包含两个整数 $a_i, b_i$，表示存在一扇门连接房间 $a_i$ 和 $b_i$，该门由钥匙 $i$ 打开。

首先输出两行，表示钥匙的分配情况。然后输出 Alice 和 Bob 的所有指令，如题目描述，每行一条。如果无解，则输出 `"No solution"`（不带引号）。如果存在多组合法解，则任意一组均可接受。

### 注释 第一个样例对应如下的平面图，其中蓝色数字表示打开每扇门所需的钥匙编号： :::align{center}  ::: Alice 拿走钥匙 $0$、$1$ 和 $2$，而 Bob 拿走钥匙 $3$ 和 $4$。Alice 从 $0$ 走到 $1$，再到 $2$，再到 $3$。在那里，她丢下钥匙 $0$。然后她沿原路返回 $1$。Bob 从 $1$ 出发，走到 $4$，再到 $3$，在那捡到钥匙 $0$。然后他沿原路返回 $1$，再利用新捡到的钥匙 $0$ 打开通往 $0$ 的门。 在第二个样例中，Alice 和 Bob 都无法顺利到达目的地。注意，Alice 不能在房间 $1$ 丢下钥匙。 ### 输入输出限制 - $2 \leq n, m \leq 10^5$ - $0 \leq a_i, b_i < n$ - 保证如果拥有全部钥匙，则一定可以从任意房间到达任意房间。 - 任意一对房间之间最多只有一扇门。 - 没有房间会与自身相连。 - 你的程序最多可以输出 $4 \cdot 10^5$ 条指令。 --- 翻译由 ChatGPT-5 完成