# CF612E Square Root of Permutation

• 8通过
• 12提交
• 题目来源
• 评测方式 RemoteJudge
• 标签
• 难度 省选/NOI-
• 时空限制 2000ms / 256MB
• 提示：收藏到任务计划后，可在首页查看。

## 题意翻译

给定一个$n$的排列$p_i$，求一个排列$q_i$，使得对于任意$1\leq i\leq n$，$q_{q_i}=p_i$。无解输出$-1$。

$1\leq n\leq10^6$。

## 题目描述

A permutation of length $n$ is an array containing each integer from $1$ to $n$ exactly once. For example, $q=[4,5,1,2,3]$ is a permutation. For the permutation $q$ the square of permutation is the permutation $p$ that $p[i]=q[q[i]]$ for each $i=1...\ n$ . For example, the square of $q=[4,5,1,2,3]$ is $p=q^{2}=[2,3,4,5,1]$ .

This problem is about the inverse operation: given the permutation $p$ you task is to find such permutation $q$ that $q^{2}=p$ . If there are several such $q$ find any of them.

## 输入输出格式

输入格式：

The first line contains integer $n$ ( $1<=n<=10^{6}$ ) — the number of elements in permutation $p$ .

The second line contains $n$ distinct integers $p_{1},p_{2},...,p_{n}$ ( $1<=p_{i}<=n$ ) — the elements of permutation $p$ .

输出格式：

If there is no permutation $q$ such that $q^{2}=p$ print the number "-1".

If the answer exists print it. The only line should contain $n$ different integers $q_{i}$ ( $1<=q_{i}<=n$ ) — the elements of the permutation $q$ . If there are several solutions print any of them.

## 输入输出样例

输入样例#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

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。