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 ```