Căn bậc hai của hoán vị

Một hoán vị độ dài $n$ là một dãy chứa mỗi số nguyên từ $1$ đến $n$ đúng một lần. Với hoán vị $q$, ta định nghĩa bình phương của $q$ là hoán vị $p$ sao cho:

$$p_i=q_{q_i}\text{với mọi }i=1,2,\dots ,n.$$

Ví dụ, bình phương của $q=[4,5,1,2,3]$ là $p=[2,3,4,5,1]$.

Cho hoán vị $p$, hãy tìm một hoán vị $q$ sao cho bình phương của $q$ bằng $p$ (tức $q_{q_i}=p_i$ với mọi $i$). Nếu có nhiều đáp án, in ra bất kỳ. Nếu không tồn tại $q$ nào thỏa mãn, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$, số phần tử của hoán vị $p$.
• Dòng thứ hai chứa $n$ số nguyên phân biệt $p_1,p_2,\dots ,p_n$.

Dữ liệu ra

• Nếu không tồn tại hoán vị $q$ thỏa mãn, in ra $-1$.
• Ngược lại, in ra $n$ số nguyên phân biệt $q_1,q_2,\dots ,q_n$ là các phần tử của hoán vị $q$. Nếu có nhiều đáp án, in ra bất kỳ đáp án hợp lệ nào.

Ràng buộc

• $1\le n\le {10}^6$
• $1\le p_i\le n$ và các $p_i$ đôi một phân biệt.

Ví dụ