P13926 [POKATT 2024] 猫和老鼠 / KATT:s and rats

**这是一道交互题**。本题中，交互库是非自适应的。 一种特殊的变异巨鼠占领了哥德堡的下水道，城市管理部门请求你帮助解决这个问题。 下水道系统由 $N$ 个沙井（编号从 $1$ 到 $N$）和 $N-1$ 条连接沙井的管道组成。每条管道连接两个沙井，并且下水道的设计保证了任意两个沙井之间都可以通过一系列管道相连通。为了节约成本，哥德堡所有的下水道开发人员都已被解雇，导致整个下水道系统完全没有文档记录。这意味着没有人知道哪些沙井之间有管道直接相连。 下水道中总共有 $K$ 只变异巨鼠，它们位于不同的沙井中。由于这些老鼠体型巨大且极具攻击性，同一个沙井里永远不会有两只老鼠。你已经在不同的沙井里放置了 $K$ 个 KATT（动能激活绊倒陷阱）。这些陷阱可以通过一个按钮同时激活，而你现在的目标就是想办法让老鼠们移动到有 KATT 的沙井里。但是，这些老鼠非常聪明，如果不是所有 KATT 同时被激活，它们会学会利用 KATT 来对付你。 为了让老鼠移动，你有大量的 OWL（全向声波发射器），它们可以播放对这种变异巨鼠特别刺激的歌曲和噪音。你可以分多轮选择一部分沙井，在每个选定的沙井中放置一个 OWL。在每一轮中，你放置一些 OWL，然后一些老鼠可能会为了躲避烦人的声音而穿过管道。具体来说，每只老鼠都有机会逃跑，并且根据物理定律，老鼠们会按照它们当前所在沙井的编号从小到大的顺序行动。也就是说，如果沙井 $1$ 和沙井 $2$ 中都有老鼠，那么沙井 $1$ 中的老鼠会先尝试逃跑。当这只老鼠完成逃跑后，沙井 $2$ 中的老鼠才会开始它的逃跑。 老鼠们希望最大化与最近的 OWL 之间的距离。一只老鼠会考虑移动到与它当前位置相距一条管道之遥的所有没有其他老鼠的沙井。如果这些沙井中没有一个到最近 OWL 的距离严格大于当前位置的距离，那么这只老鼠会停在原地。否则，它会移动到那个能提供到最近 OWL 的最大距离的相邻沙井。如果有多个这样的沙井，它会选择其中编号最小的那个。两个沙井之间的距离是指连接它们所需经过的最少管道数。 你从哥德堡市获得了大量的 OWL，但在变异巨鼠的繁殖季节开始之前（这会带来灾难性的后果！），你最多只能进行 $25000$ 轮 OWL 的放置。 ### 实现细节 首先，你的程序应该读取一行中的两个数字 $N$ ($2 \leq N \leq 100$) 和 $K$ ($1 \leq K < N$)。 接下来一行是 $K$ 个不同的数字 $1 \leq r_1 < ... < r_K \leq N$，描述了老鼠的初始位置所在的沙井编号。 然后一行是 $K$ 个不同的数字 $1 \leq t_1 < ... < t_K \leq N$，描述了放置了 KATT 的沙井编号。 当你想进行一轮 OWL 放置时，你应该首先输出一个数字 $M$，表示你本轮放置的 OWL 数量。然后在同一行上，输出 $M$ 个数字 $1 \leq s_1 < ... < s_M \leq N$，表示你希望放置 OWL 的沙井编号。无论沙井中是否有老鼠，都可以放置 OWL。 然后，你的程序应该读取一行包含 $K$ 个数字 $1 \leq r_1 < ... < r_K \leq N$，表示在所有老鼠尝试逃离声音之后，它们所在的新位置。 当你成功地将所有老鼠移动到有 KATT 的沙井时，你应该输出一行 “`activate!`”。 然后你的程序应该终止。 **请务必在每次查询后刷新输出**，否则你可能会得到 *Time Limit Exceeded* 的判决。 在 C++ 中，可以使用 `cout

见「实现细节」。 注意：保证**老鼠的初始位置和 KATT 的放置位置是均匀随机选择的**。但是下水道的结构不一定是随机生成的。

见「实现细节」。

### 样例解释 #### 样例 $2$ 解释  **图 1：** 样例 2 中的下水道布局。请注意，你的程序不会知道管道的布局。  **图 2：** 当你在沙井 4 和 5 放置 OWL 时，老鼠们会非常不安。首先，由于 $4 < 5$，沙井 4 中的老鼠会尝试逃跑。这只老鼠会移动到沙井 3。之后，沙井 5 中的老鼠尝试逃跑，但没有可用的沙井可以去。  **图 3：** 当你在沙井 5 放置一个 OWL 时，首先沙井 3 中的老鼠逃到沙井 2，然后沙井 5 中的老鼠逃到沙井 3。  **图 4：** 当你再次在沙井 5 放置一个 OWL 时，首先沙井 2 中的老鼠逃到沙井 1，然后沙井 3 中的老鼠逃到沙井 2。  **图 5：** 现在所有老鼠都位于有 KATT 的沙井中，因此你可以激活 KATT。 ### 子任务 **本题采用捆绑测试。** | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ | $5 $| $N = 2$ | | $2$ | $5 $| $N \leq 3$ | | $3$ | $9 $| $N \leq 10$ | | $4$ | $20$ | $K = 1$ | | $5$ | $15$ | 对于所有 $1 \leq i < N$，沙井 $i$ 和沙井 $i+1$ 之间有一条管道。 | | $6$ | $21$ | $N \leq 50$ | | $7$ | $25$ | 无额外限制。 |