Description

Google 编程竞赛团队正在筹建一个新的主题公园。和所有优秀的主题公园一样，我们希望让演员装扮成吉祥物与游客互动。由于开业在即，我们决定使用 CODE JAM、KICK START 和 HASH CODE 中的字母作为吉祥物，共计 13 种不同的吉祥物（字母 ACDEHIJKMORST）。

公园唯一的景点是一个由 $\mathbf{N}$ 个房间组成的迷宫，房间编号从 1 到 $\mathbf{N}$。每个房间都有一个左出口和一个右出口。每个出口会将游客带到另一个房间。出口不能反向使用；例如，如果房间 2 有一个出口通向房间 3，你不能从房间 3 返回到房间 2，除非房间 3 恰好也有一个出口通向房间 2。

我们希望在每个房间放置恰好一个这 13 种吉祥物。每个字母可以在迷宫的零个、一个或多个房间中出现。为了增加多样性，我们希望这样放置吉祥物：游客连续访问的任意三个（不一定不同）房间中的吉祥物必须互不相同。

你能帮助我们为每个房间选择一个吉祥物来满足这一目标吗？或者告诉我们这是不可能实现的？

Input Format

输入的第一行给出测试用例的数量 $\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$。

Output Format

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

4
3
2 1 1
3 3 2
6
3 1 4 1 2 3
5 3 5 2 4 5
20
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 1
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 2
19
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 1
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19 3

Case #1: IMPOSSIBLE
Case #2: TSHIRT
Case #3: HCJKSHCJKSHCJKSHCJKS
Case #4: CODEJAMROCKSTHEMOST

Hint

样例解释

样例 #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 完成