{"problem":{"name":"C. Arpa's loud Owf and Mehrdad's evil plan","description":{"content":"_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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF742C"},"statements":[{"statement_type":"Markdown","content":"_As you have noticed, there are lovely girls in Arpa’s land._\n\nPeople 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_.\n\n<center>![image](https://espresso.codeforces.com/20529eb7f1d4e30940b606486759124a9c93edca.png)</center>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.\n\nThe 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.\n\nMehrdad 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.\n\nSome strange fact in Arpa's land is that someone can be himself's crush (i.e. _crush__i_ = _i_).\n\n## Input\n\nThe first line of input contains integer _n_ (1 ≤ _n_ ≤ 100) — the number of people in Arpa's land.\n\nThe second line contains _n_ integers, _i_\\-th of them is _crush__i_ (1 ≤ _crush__i_ ≤ _n_) — the number of _i_\\-th person's crush.\n\n## Output\n\nIf there is no _t_ satisfying the condition, print _\\-1_. Otherwise print such smallest _t_.\n\n[samples]\n\n## Note\n\nIn the first sample suppose _t_ = 3.\n\nIf the first person starts some round:\n\nThe 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.\n\nThe process is similar for the second and the third person.\n\nIf the fourth person starts some round:\n\nThe 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.\n\nIn the last example if the first person starts a round, then the second person becomes the Joon-Joon, and vice versa.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"正如你所注意到的，Arpa 的土地上有许多可爱的女孩。\n\nArpa 土地上的人从 #cf_span[1] 编号到 #cf_span[n]。每个人都有且仅有一个暗恋对象，第 #cf_span[i] 个人的暗恋对象是编号为 #cf_span[crushi] 的人。\n\n某一天，Arpa 从宫殿顶上大声喊出 _Owf_，于是 Arpa 的土地上开始了一个有趣的游戏。游戏规则如下：\n\n游戏由若干轮组成。假设第 #cf_span[x] 个人想开始一轮，他拨打 #cf_span[crushx] 的电话并说：\"_Oww...wwf_\"（字母 _w_ 重复 #cf_span[t] 次），然后立即挂断电话。如果 #cf_span[t > 1]，则 #cf_span[crushx] 拨打 #cf_span[crushcrushx] 的电话并说：\"_Oww...wwf_\"（字母 _w_ 重复 #cf_span[t - 1] 次），然后立即挂断电话。这一过程持续进行，直到某个人接收到 \"_Owf_\"（即 #cf_span[t = 1]）。这个接收到 \"_Owf_\" 的人被称为该轮的 _Joon-Joon_。同一时间只能进行一轮游戏。\n\nMehrdad 有一个邪恶的计划，想让这个游戏更有趣：他希望找到最小的 #cf_span[t]（#cf_span[t ≥ 1]），使得对于每个人 #cf_span[x]，如果 #cf_span[x] 开始某一轮，而 #cf_span[y] 成为该轮的 Joon-Joon，那么从 #cf_span[y] 开始一轮时，#cf_span[x] 将成为该轮的 Joon-Joon。如果可能，请找出这样的最小 #cf_span[t]。\n\nArpa 土地上的一个奇怪事实是：某人可以暗恋自己（即 #cf_span[crushi = i]）。\n\n输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）——Arpa 土地上的人数。\n\n第二行包含 #cf_span[n] 个整数，第 #cf_span[i] 个整数是 #cf_span[crushi]（#cf_span[1 ≤ crushi ≤ n]）——第 #cf_span[i] 个人的暗恋对象编号。\n\n如果不存在满足条件的 #cf_span[t]，请输出 _-1_。否则输出满足条件的最小 #cf_span[t]。\n\n在第一个样例中，假设 #cf_span[t = 3]：\n\n如果第一个人开始一轮：\n\n第一个人拨打第二个人的电话，说 \"_Owwwf_\"，然后第二个人拨打第三个人的电话，说 \"_Owwf_\"，接着第三个人拨打第一个人的电话，说 \"_Owf_\"，因此第一个人成为该轮的 Joon-Joon。所以当 #cf_span[x] 为 #cf_span[1] 时，条件成立。\n\n对于第二个人和第三个人，过程类似。\n\n如果第四个人开始一轮：\n\n第四个人拨打自己的电话，说 \"_Owwwf_\"，然后再次拨打自己的电话，说 \"_Owwf_\"，接着第三次拨打自己的电话，说 \"_Owf_\"，因此第四个人成为该轮的 Joon-Joon。所以当 #cf_span[x] 为 #cf_span[4] 时，条件成立。\n\n在最后一个样例中，如果第一个人开始一轮，则第二个人成为 Joon-Joon，反之亦然。\n\n## Input\n\n输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）——Arpa 土地上的人数。\n\n第二行包含 #cf_span[n] 个整数，第 #cf_span[i] 个整数是 #cf_span[crushi]（#cf_span[1 ≤ crushi ≤ n]）——第 #cf_span[i] 个人的暗恋对象编号。\n\n## Output\n\n如果不存在满足条件的 #cf_span[t]，请输出 _-1_。否则输出满足条件的最小 #cf_span[t]。\n\n[samples]\n\n## Note\n\n在第一个样例中，假设 #cf_span[t = 3]：如果第一个人开始一轮：第一个人拨打第二个人的电话，说 \"_Owwwf_\"，然后第二个人拨打第三个人的电话，说 \"_Owwf_\"，接着第三个人拨打第一个人的电话，说 \"_Owf_\"，因此第一个人成为该轮的 Joon-Joon。所以当 #cf_span[x] 为 #cf_span[1] 时，条件成立。对于第二个人和第三个人，过程类似。如果第四个人开始一轮：第四个人拨打自己的电话，说 \"_Owwwf_\"，然后再次拨打自己的电话，说 \"_Owwf_\"，接着第三次拨打自己的电话，说 \"_Owf_\"，因此第四个人成为该轮的 Joon-Joon。所以当 #cf_span[x] 为 #cf_span[4] 时，条件成立。在最后一个样例中，如果第一个人开始一轮，则第二个人成为 Joon-Joon，反之亦然。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of people.  \nLet $ f: \\{1, \\dots, n\\} \\to \\{1, \\dots, n\\} $ be the crush function, where $ f(i) $ is the crush of person $ i $.  \n\nFor $ t \\in \\mathbb{Z}^+ $, define the $ t $-step function $ f^t $ as the $ t $-fold composition of $ f $:  \n$ f^1(i) = f(i) $, $ f^{k}(i) = f(f^{k-1}(i)) $ for $ k \\geq 2 $.  \n\nA person $ x $ starting a round with parameter $ t $ results in Joon-Joon $ y = f^t(x) $.  \n\n**Constraint**  \nFor all $ x \\in \\{1, \\dots, n\\} $, if $ y = f^t(x) $, then $ x = f^t(y) $.  \n\n**Objective**  \nFind the smallest $ t \\geq 1 $ such that:  \n$$\n\\forall x \\in \\{1, \\dots, n\\}, \\quad f^t(f^t(x)) = x\n$$  \nIf no such $ t $ exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF742C","tags":["dfs and similar","math"],"sample_group":[["4\n2 3 1 4","3"],["4\n4 4 4 4","\\-1"],["4\n2 1 4 3","1"]],"created_at":"2026-03-03 11:00:39"}}