codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

741A.md (2921B)


      1 Source: https://codeforces.com/problemset/problem/741/A
      2 
      3 A. Arpa's loud Owf and Mehrdad's evil plan
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 As you have noticed, there are lovely girls in Arpa’s land.
     22 
     23 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*.
     24 
     25  ![](https://espresso.codeforces.com/20529eb7f1d4e30940b606486759124a9c93edca.png) 
     26 
     27 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.
     28 
     29 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.
     30 
     31 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.
     32 
     33 Some strange fact in Arpa's land is that someone can be himself's crush (i.e. *crush**i* = *i*).
     34 
     35 Input
     36 
     37 The first line of input contains integer *n* (1 ≤ *n* ≤ 100) — the number of people in Arpa's land.
     38 
     39 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.
     40 
     41 Output
     42 
     43 If there is no *t* satisfying the condition, print -1. Otherwise print such smallest *t*.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 4  
     51 2 3 1 4
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 3
     58 ```
     59 
     60 Input
     61 
     62 ```
     63 4  
     64 4 4 4 4
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 -1
     71 ```
     72 
     73 Input
     74 
     75 ```
     76 4  
     77 2 1 4 3
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 1
     84 ```
     85 
     86 Note
     87 
     88 In the first sample suppose *t* = 3.
     89 
     90 If the first person starts some round:
     91 
     92 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.
     93 
     94 The process is similar for the second and the third person.
     95 
     96 If the fourth person starts some round:
     97 
     98 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.
     99 
    100 In the last example if the first person starts a round, then the second person becomes the Joon-Joon, and vice versa.