← 返回题目列表

Codeforces · 612/E

E. 排列的平方根

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

长度为 n 的排列是一个数组,其中包含从 1 到 n 的每个整数恰好一次。例如,q = [4, 5, 1, 2, 3] 是一个排列。对于排列 q,排列的平方是排列 p,对于每个 i = 1... n,p[i] = q[q[i]]。例如,q = [4, 5, 1, 2, 3] 的平方为 p = q2 = [2, 3, 4, 5, 1]。

这个问题是关于逆运算的:给定排列 p,你的任务是找到满足 q2 = p 的排列 q。如果有几个这样的q,找出其中的任何一个。

输入

第一行包含整数 n (1 ≤ n ≤ 106) — 排列 p 中的元素数量。

第二行包含 n 个不同的整数 p1, p2, ..., pn (1 ≤ pi ≤ n) — 排列 p 的元素。

输出

如果没有排列 q 使得 q2 = p 打印数字“-1”。

如果答案存在,请将其打印出来。唯一的一行应包含 n 个不同的整数 qi (1 ≤ qi ≤ n) — 排列 q 的元素。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

4
2 1 4 3

输出 #1

3 4 2 1

输入 #2

4
2 1 3 4

输出 #2

-1

输入 #3

5
2 3 4 5 1

输出 #3

4 5 1 2 3