codeforces742CArpa's loud Owf and Mehrdad's evil plan 【强连通】

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

Someday Arpa shouted Owf loudly from the top of the palace and a funny game started in Arpa's land. The rules are as follows.

The game consists of rounds. Assume person x wants to start a round, he calls crush_x and says: "Oww...wwf" (the letter w is repeated t times) and cuts off the phone immediately. If t > 1 then crush_x calls crush_{crush_x} and says: "Oww...wwf" (the letter w is repeated t - 1 times) and cuts off the phone immediately. The round continues until some person receives an "Owf" (t = 1). This person is called the Joon-Joon of the round. There can't be two rounds at the same time.

Mehrdad has an evil plan to make the game more funny, he wants to find smallest t (t ≥ 1) such that for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y, x would become the Joon-Joon of the round. Find such t for Mehrdad if it's possible.

Some strange fact in Arpa's land is that someone can be himself's crush (i.e. crush_i = i).

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 crush_i (1 ≤ crush_i ≤ 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

Input

4 4 4 4 4

Output

-1

Input

4 2 1 4 3

Output

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.

好像有两个月没刷题了==脑子已经从短路到断路了QAQ

题意：（都没读明白）对于给定的一个数列 nxt[n] ,如果现在点 i ，那么下一个点就在 nxt[i] ，现在问给定 n 个，找到一个最小的 t ,使得对于从任意一个点 x 出发，经过 t 次之后，到达的点 y , 使得点 y 经过 t 次之后会回到点 x .

做法：

首先判断无解的情况：
对于图中的所有点，有且仅有一条出边，那么如果能成环，那么将有且仅有一条入边，若不满足，则无解
有解情况讨论：
如果环为长度为k的奇环，那么得经过k（只能回到自己）
如果环为长度为k的偶环，那么只需要经过k / 2

则先跑强连通分量对所有点编号，得到所有环的长度，然后求它们的最小公倍数即可

看完题解就很不理解啊，为啥找环就要找强连通分量，强连通分量里面有很多环啊，怎么数个数啊。

这个题限制了一个关键的条件：每个点只有一条有向边！！所以强连通分量就是一个环！！

#include<cstdio> #include<cstring> #include<vector> #include<stack> using namespace std; int num[110],n; int gcd(int a,int b) { return b?gcd(b,a%b):a; } vector<int>G[110]; int pre[110],lowlink[110],sccno[110],dfs_clock,scc_cnt; stack<int>S; int min(int a,int b){if(a<b)return a;return b;} int in[110]; void dfs(int u) { pre[u]=lowlink[u]=++dfs_clock; S.push(u); for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(!pre[v]) { dfs(v); lowlink[u]=min(lowlink[u],lowlink[v]); } else if(!sccno[v]) lowlink[u]=min(lowlink[u],pre[v]); } if(lowlink[u]==pre[u]) { scc_cnt++; for(;;) { int x=S.top();S.pop(); sccno[x]=scc_cnt; if(x==u) break; } } } void find_scc(int n) { dfs_clock=scc_cnt=0; memset(sccno,0,sizeof(sccno)); memset(pre,0,sizeof(pre)); for(int i=1;i<=n;i++) if(!pre[i]) dfs(i); } int main() { int n; //freopen("cin.txt","r",stdin); while(~scanf("%d",&n)) { int ans=1; for(int i=1;i<=n;i++)G[i].clear(); memset(num,0,sizeof(num)); memset(in,0,sizeof(in)); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); G[i].push_back(x); in[i]++; in[x]++; } find_scc(n); for(int i=1;i<=n;i++)num[sccno[i]]++; for(int i=1;i<=scc_cnt;i++) { if(num[i]&1) ans=ans/gcd(ans,num[i])*num[i]; else { num[i]/=2; ans=ans/gcd(ans,num[i])*num[i]; } } for(int i=1;i<=n;i++) { if(in[i]!=2)ans=-1; } printf("%d\n",ans); } }

今天的文章 codeforces742CArpa's loud Owf and Mehrdad's evil plan 【强连通】分享到此就结束了，感谢您的阅读。

codeforces742CArpa's loud Owf and Mehrdad's evil plan 【强连通】

相关推荐