codeforces-scrape

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

285B.md (2151B)


      1 Source: https://codeforces.com/problemset/problem/285/B
      2 
      3 B. Find Marble
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Petya and Vasya are playing a game. Petya's got *n* non-transparent glasses, standing in a row. The glasses' positions are indexed with integers from 1 to *n* from left to right. Note that the positions are indexed but the glasses are not.
     22 
     23 First Petya puts a marble under the glass in position *s*. Then he performs some (possibly zero) shuffling operations. One shuffling operation means moving the glass from the first position to position *p*1, the glass from the second position to position *p*2 and so on. That is, a glass goes from position *i* to position *p**i*. Consider all glasses are moving simultaneously during one shuffling operation. When the glasses are shuffled, the marble doesn't travel from one glass to another: it moves together with the glass it was initially been put in.
     24 
     25 After all shuffling operations Petya shows Vasya that the ball has moved to position *t*. Vasya's task is to say what minimum number of shuffling operations Petya has performed or determine that Petya has made a mistake and the marble could not have got from position *s* to position *t*.
     26 
     27 Input
     28 
     29 The first line contains three integers: *n*, *s*, *t* (1 ≤ *n* ≤ 105; 1 ≤ *s*, *t* ≤ *n*) — the number of glasses, the ball's initial and final position. The second line contains *n* space-separated integers: *p*1, *p*2, ..., *p**n* (1 ≤ *p**i* ≤ *n*) — the shuffling operation parameters. It is guaranteed that all *p**i*'s are distinct.
     30 
     31 Note that *s* can equal *t*.
     32 
     33 Output
     34 
     35 If the marble can move from position *s* to position *t*, then print on a single line a non-negative integer — the minimum number of shuffling operations, needed to get the marble to position *t*. If it is impossible, print number -1.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 4 2 1  
     43 2 3 4 1
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 3
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 4 3 3  
     56 4 1 3 2
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 0
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 4 3 4  
     69 1 2 3 4
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 -1
     76 ```
     77 
     78 Input
     79 
     80 ```
     81 3 1 3  
     82 2 1 3
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 -1
     89 ```