CF612E.Square Root of Permutation

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.

长度为 $n$ 的排列是指恰好包含从 $1$ 到 $n$ 的每个整数各一次的数组。例如，$q = [4, 5, 1, 2, 3]$ 是一个排列。对于排列 $q$，其平方定义为排列 $p$，满足对每个 $i = 1,\dots,n$，都有 $p[i] = q[q[i]]$。例如，$q = [4, 5, 1, 2, 3]$ 的平方为 $p = q^2 = [2, 3, 4, 5, 1]$。

本题要求执行逆运算：给定排列 $p$，请找出一个排列 $q$，使得 $q^2 = p$。若存在多个满足条件的 $q$，输出任意一个即可。

The first line contains integer n (1 ≤ n ≤ 106) — 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.

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）—— 排列 $p$ 中的元素个数。

第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$）—— 排列 $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.

如果不存在排列 $q$ 使得 $q^2 = p$，则输出数字 $-1$。

如果答案存在，请输出它。唯一的一行应包含 $n$ 个互不相同的整数 $q_i$（$1 \le q_i \le n$）——即排列 $q$ 的各个元素。若存在多个解，输出任意一个即可。