301510: CF285B. Find Marble

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Find Marble

题目描述

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. 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. 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 $ .

输入输出格式

输入格式


The first line contains three integers: $ n,s,t\ (1<=n<=10^{5}; 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. Note that $ s $ can equal $ t $ .

输出格式


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.

输入输出样例

输入样例 #1

4 2 1
2 3 4 1

输出样例 #1

3

输入样例 #2

4 3 3
4 1 3 2

输出样例 #2

0

输入样例 #3

4 3 4
1 2 3 4

输出样例 #3

-1

输入样例 #4

3 1 3
2 1 3

输出样例 #4

-1

Input

题意翻译

给出一个长度为 $n$ 的排列 $p$ 以及两个在 $[1,n]$ 中的整数 $s$、$t$。 定义对 $x$ 的一次操作为使 $x$ 变为 $p_x$。 求将 $s$ 变为 $t$ 最少需要几次操作?

加入题单

上一题 下一题 算法标签: