← 返回题目列表

Codeforces · 1773/A

A. 惊人的把戏

中文机器翻译题面 查看原题

爱丽丝是一位魔术师,她创造了一个新魔术。她有 $$$n$$$ 卡片,上面写着从 $$$1$$$ 到 $$$n$$$ 的不同数字。首先,她要求一位观众洗牌并将牌排成一排。假设左边第 $$$i$$$ 卡上有数字 $$$a_i$$$。

然后 Alice 选择两个排列 $$$p$$$ 和 $$$q$$$。 $$$p$$$ 和 $$$q$$$ 有限制 — 排列不能有固定点。这意味着$$$\forall i: p_i \ne i\ 和\ q_i \ne i$$$。

选择排列后,爱丽丝根据排列洗牌。现在从左边算起第$$$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$$$。

输出

按照案例在输入中出现的顺序打印每个测试案例的答案。

对于每个测试用例,打印“不可能" 在一行中,如果不存在解决方案。

否则,打印“可能" 在第一行,在接下来的两行中打印排列 $$$p$$$ 和 $$$q$$$。

示例

输入
复制

4
2
2 1
3
1 2 3
4
2 1 4 3
5
5 1 4 2 3

输出
复制

Impossible
Possible
3 1 2
2 3 1
Possible
3 4 2 1
3 4 2 1
Possible
4 1 2 5 3
3 1 4 5 2