P12999 [GCJ 2022 #3] Mascot Maze

Google 编程竞赛团队正在筹建一个新的主题公园。和所有优秀的主题公园一样，我们希望让演员装扮成吉祥物与游客互动。由于开业在即，我们决定使用 CODE JAM、KICK START 和 HASH CODE 中的字母作为吉祥物，共计 13 种不同的吉祥物（字母 `ACDEHIJKMORST`）。 公园唯一的景点是一个由 $\mathbf{N}$ 个房间组成的迷宫，房间编号从 1 到 $\mathbf{N}$。每个房间都有一个左出口和一个右出口。每个出口会将游客带到另一个房间。出口不能反向使用；例如，如果房间 2 有一个出口通向房间 3，你不能从房间 3 返回到房间 2，除非房间 3 恰好也有一个出口通向房间 2。  我们希望在每个房间放置恰好一个这 13 种吉祥物。每个字母可以在迷宫的零个、一个或多个房间中出现。为了增加多样性，我们希望这样放置吉祥物：游客连续访问的任意三个（不一定不同）房间中的吉祥物必须互不相同。 你能帮助我们为每个房间选择一个吉祥物来满足这一目标吗？或者告诉我们这是不可能实现的？

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例包含 3 行。第一行是一个整数 $\mathbf{N}$，表示迷宫中的房间数量。第二行包含 $\mathbf{N}$ 个整数 $\mathbf{L}_1, \mathbf{L}_2, \ldots, \mathbf{L}_\mathbf{N}$，表示房间 $i$ 的左出口通向房间 $\mathbf{L}_i$。第三行包含 $\mathbf{N}$ 个整数 $\mathbf{R}_1, \mathbf{R}_2, \ldots, \mathbf{R}_\mathbf{N}$，表示房间 $i$ 的右出口通向房间 $\mathbf{R}_i$。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 `IMPOSSIBLE`（如果无法按照上述规则分配吉祥物）。否则，$y$ 是一个长度为 $\mathbf{N}$ 的字符串，其第 $i$ 个字符是大写字母 `ACDEHIJKMORST` 中的一个，表示你希望分配给第 $i$ 个房间的吉祥物。

**样例解释** 样例 #1 对应题目描述中的图片。游客可以连续访问房间 1、2、1（其中房间 1 被访问两次），因此这种情况不可能满足要求。 样例 #2 的布局如下（蓝色箭头表示左出口，红色箭头表示右出口）：  众多有效解之一如输出所示。注意虽然我们不需要分配两个 $\tau$ 吉祥物，但当前的分配方式不会违反规则。 样例 #3 和 #4 是可行的，但需要重复使用某些吉祥物。 **限制** - $1 \leq \mathbf{T} \leq 100$。 - 对于所有 $i$，$\mathbf{L}_i \neq i$ 且 $\mathbf{R}_i \neq i$。 - 对于所有 $i$，$1 \leq \mathbf{L}_i < \mathbf{R}_i \leq \mathbf{N}$。 **测试集 1（12 分，可见判题结果）** - 时间限制：20 秒。 - $3 \leq \mathbf{N} \leq 100$。 **测试集 2（13 分，隐藏判题结果）** - 时间限制：45 秒。 - $3 \leq \mathbf{N} \leq 10^5$。 翻译由 DeepSeek V3 完成