D - Arpa's loud Owf and Mehrdad's evil plan

Codeforces Round #383 (Div. 2)

As you have noticed, there are lovely girls in Arpa’s land.
People in Arpa's land are numbered from 1 to n. Everyone has exactly one crush, i-th person's crush is person with the number crushi
.

Input
The first line of input contains integer n (1 ≤ n ≤ 100) — the number of people in Arpa's land.
The second line contains n integers, i-th of them is crushi (1 ≤ crushi ≤ n) — the number of i-th person's crush.

Output
If there is no t satisfying the condition, print -1. Otherwise print such smallest t.

Example
Input
4
2 3 1 4

Output
3

Input
4
4 4 4 4

Output
-1

Input
4
2 1 4 3

Output
1

Note
In the first sample suppose t = 3.
If the first person starts some round:
The first person calls the second person and says "Owwwf", then the second person calls the third person and says "Owwf", then the third person calls the first person and says "Owf", so the first person becomes Joon-Joon of the round. So the condition is satisfied if x is 1.
The process is similar for the second and the third person.
If the fourth person starts some round:
The fourth person calls himself and says "Owwwf", then he calls himself again and says "Owwf", then he calls himself for another time and says "Owf", so the fourth person becomes Joon-Joon of the round. So the condition is satisfied when x is 4.
In the last example if the first person starts a round, then the second person becomes the Joon-Joon, and vice versa.

题意：一个有向图，使任意从结点a到结点b的距离等于结点b到结点a的距离，问这个距离最小值是多少

解法：对于每个节点的出度和入度一定为1，否者不可能实现，那么图为很多个环，对于奇数环最下距离为节点数，偶数环最下距离为节点数的一半，求所有最小距离的最小公倍数

代码·：

#include<iostream>
using namespace std;
int a[105],cnt=0;
bool vis[105];
int mi(int x,int y){
    return y?mi(y,x%y):x;
}
int ma(int x,int y){
    return x/mi(x,y)*y;
}
int dfs(int x){
    int c=1,next=a[x];
    vis[x]=0;
    while(1){
        vis[next]=1;
        if(next==x)
            break;
        next=a[next];
        c++;
    }
    return c;
}
int main()
{
    int n,flag=0,ans;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(vis[a[i]]==0)
            vis[a[i]]=1;
        else
            flag=1;
    }
    if(flag==1){
        cout<<-1<<endl;
        return 0;
    }
    ans=dfs(1);
    if(ans%2==0)
        ans/=2;
    for(int i=1;i<=n;i++){
        if(vis[i]==1){
            int now=dfs(i);
            if(now%2==0)
                now/=2;
            ans=ma(ans,now);
        }
    }
    cout<<ans<<endl;
}