CodeForces - 612E （置换群）

本是古典何须时尚 2022-05-29 12:10 190阅读 0赞

E. Square Root of Permutation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Input

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*.

Output

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.

Examples

input

Copy

4
    2 1 4 3

output

3 4 2 1

input

Copy

4
    2 1 3 4

output

-1

input

Copy

5
    2 3 4 5 1

output

4 5 1 2 3

不太理解  引用一下别人代码

#include<cstdio>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    using namespace std;
    const int maxn=1e6+10;
    int num[maxn];
    vector<int> v[maxn];
    int n, vis[maxn], ans[maxn], id[maxn];
    
    bool cmp(vector<int> &a, vector<int> &b){
    	
    	return a.size()<b.size();
    }
    
    int main(){
    	int n;
    	scanf("%d", &n);
    	
    	for(int i=1; i<=n; i++)
    		scanf("%d", &num[i]);
    	
    	int cnt=0;
    	
    	for(int i=1; i<=n; i++)
    	{
    		if(vis[i]) continue;
    		int now=i;
    		++cnt;
    		do{
    			vis[now]=1;
    			v[cnt].push_back(now);
    			now=num[now];
    		}while(now!=i);
    	}
    	
    	sort(v+1, v+1+cnt, cmp);
    	for(int i=1; i<=cnt; i++){
    		int sz=v[i].size();
    		
    		if(sz & 1){
    			for(int j=0; j<sz; j++)
    				id[j*2%sz]=v[i][j];
    			for(int j=0; j<sz; j++)
    				ans[id[j]] = id[(j+1)%sz];
    		}
    		else if(sz == v[i+1].size()){
    			for(int j=0; j<sz; j++)
    			{
    				ans[v[i][j]]=v[i+1][j];
    				ans[v[i+1][j]] = v[i][(j+1)%sz];
    			}
    			i++;
    		}
    		else{
    			puts("-1");
    			return 0;
    			
    		}
    		
    	}	
    	for(int i=1; i<=n; i++)
    		printf("%d%s", ans[i], i==n?"\n":" ");
    	return 0;
    }