CF1773A Amazing Trick

Alice 是一名魔术师，她发明了一个新魔术。她有 $n$ 张卡片，每张卡片上写着 $1$ 到 $n$ 之间的不同数字。首先，她让一名观众将卡片洗牌并排成一排。假设从左到右第 $i$ 张卡片上的数字是 $a_i$。 接着，Alice 选择两个排列 $p$ 和 $q$。对 $p$ 和 $q$ 有一个限制——排列中不能有不动点。也就是说，$\forall i: p_i \ne i$ 且 $q_i \ne i$。 选择好排列后，Alice 按照这两个排列重新洗牌。现在，从左到右第 $i$ 张卡片是 $a[p[q[i]]]$。如果洗牌后第 $i$ 张卡片上的数字是 $i$，那么魔术就算成功。 请你帮助 Alice 选择排列 $p$ 和 $q$，或者判断对于给定的初始排列 $a$ 是否不可能完成魔术。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。 每个测试用例包含两行。第一行包含一个整数 $n$——卡片的数量（$1 \leq n \leq 10^5$）。第二行包含 $n$ 个整数 $a_i$——卡片的初始排列（$1 \leq a_i \leq n$；$\forall i \neq j: a_i \neq a_j$）。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，按照输入顺序输出答案。 如果不存在解，则输出一行 "Impossible"。 否则，第一行输出 "Possible"，接下来的两行分别输出排列 $p$ 和 $q$。

由 ChatGPT 4.1 翻译