C. Arpa's loud Owf and Mehrdad's evil plan

Codeforces

IDCF742C

Time1000ms

Memory256MB

Difficulty—

dfs and similarmath

English · Original

Chinese · Translation

Formal · Original

_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_. <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. 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_. [samples] ## 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.

正如你所注意到的，Arpa 的土地上有许多可爱的女孩。 Arpa 土地上的人从 #cf_span[1] 编号到 #cf_span[n]。每个人都有且仅有一个暗恋对象，第 #cf_span[i] 个人的暗恋对象是编号为 #cf_span[crushi] 的人。某一天，Arpa 从宫殿顶上大声喊出 _Owf_，于是 Arpa 的土地上开始了一个有趣的游戏。游戏规则如下：游戏由若干轮组成。假设第 #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_。同一时间只能进行一轮游戏。 Mehrdad 有一个邪恶的计划，想让这个游戏更有趣：他希望找到最小的 #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]。 Arpa 土地上的一个奇怪事实是：某人可以暗恋自己（即 #cf_span[crushi = i]）。输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）——Arpa 土地上的人数。第二行包含 #cf_span[n] 个整数，第 #cf_span[i] 个整数是 #cf_span[crushi]（#cf_span[1 ≤ crushi ≤ n]）——第 #cf_span[i] 个人的暗恋对象编号。如果不存在满足条件的 #cf_span[t]，请输出 _-1_。否则输出满足条件的最小 #cf_span[t]。在第一个样例中，假设 #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，反之亦然。 ## Input 输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）——Arpa 土地上的人数。第二行包含 #cf_span[n] 个整数，第 #cf_span[i] 个整数是 #cf_span[crushi]（#cf_span[1 ≤ crushi ≤ n]）——第 #cf_span[i] 个人的暗恋对象编号。 ## Output 如果不存在满足条件的 #cf_span[t]，请输出 _-1_。否则输出满足条件的最小 #cf_span[t]。 [samples] ## Note 在第一个样例中，假设 #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，反之亦然。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of people. Let $ f: \{1, \dots, n\} \to \{1, \dots, n\} $ be the crush function, where $ f(i) $ is the crush of person $ i $. For $ t \in \mathbb{Z}^+ $, define the $ t $-step function $ f^t $ as the $ t $-fold composition of $ f $: $ f^1(i) = f(i) $, $ f^{k}(i) = f(f^{k-1}(i)) $ for $ k \geq 2 $. A person $ x $ starting a round with parameter $ t $ results in Joon-Joon $ y = f^t(x) $. **Constraint** For all $ x \in \{1, \dots, n\} $, if $ y = f^t(x) $, then $ x = f^t(y) $. **Objective** Find the smallest $ t \geq 1 $ such that: $$ \forall x \in \{1, \dots, n\}, \quad f^t(f^t(x)) = x $$ If no such $ t $ exists, output $ -1 $.

Samples

Input #1

4
2 3 1 4

Output #1

Input #2

4
4 4 4 4

Output #2

\-1

Input #3

4
2 1 4 3

Output #3

API Response (JSON)

{
  "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...",
      "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游戏由若干轮组成。假设...",
      "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 \\i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments