P12790 [NERC 2022] 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$。

对于每组测试数据，请按照它们在输入中出现的顺序输出答案。 对于每组测试数据，如果无解，则在单独的一行中输出 $\tt{Impossible}$。 否则，在第一行输出 $\tt{Possible}$，并在接下来的两行中分别输出排列 $p$ 和 $q$。

翻译由 gemini2.5pro 完成