挺有意思的一个构造题，不过这种排列置换相关的套路感觉都太明显了
首先考虑把原图的每个置换环求出来，稍作观察会发现所有长度为奇数的置换环都可以很容易地构造出对应的\(q\)数组
但长度为偶数的置换环就不能单独构造了，但我们发现可以把两个长度相同且为偶数的置换环交错着合并来得到一个合法的\(q\)数组
显然当某个偶数长度只存在奇数个置换环时无解，然后这题就做完了，整体思路还是很顺畅的说
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1e6+5;
int n,p[N],vis[N],ans[N]; vector <VI> len[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&p[i]);
for (i=1;i<=n;++i) if (!vis[i])
{
VI tmp; tmp.push_back(i); vis[i]=1;
for (j=p[i];j!=i;j=p[j]) tmp.push_back(j),vis[j]=1;
len[tmp.size()].push_back(tmp);
}
for (i=1;i<=n;i+=2) for (auto vec:len[i])
{
VI tmp(i); for (j=0;j<i;++j) tmp[j*2%i]=vec[j];
for (j=0;j<i;++j) ans[tmp[j]]=tmp[(j+1)%i];
}
for (i=2;i<=n;i+=2) if (len[i].size())
{
if (len[i].size()&1) return puts("-1"),0;
while (len[i].size())
{
auto x=len[i].back(); len[i].pop_back();
auto y=len[i].back(); len[i].pop_back();
for (j=0;j<i;++j) ans[x[j]]=y[j],ans[y[j]]=x[(j+1)%i];
}
}
for (i=1;i<=n;++i) printf("%d ",ans[i]);
return 0;
}