B - Trained?

Contest Duration: 2017-06-24(Sat) 12:00 - 2017-06-24(Sat) 13:40 (local time) (100 minutes) Back to Home

B - Trained? Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : $200$ 点

問題文

筋力をつけたい高橋君は、AtCoder 社のトレーニング設備で、トレーニングをすることにしました。

AtCoder 社のトレーニング設備には $N$ 個のボタンがついており、ちょうど $1$ 個のボタンが光っています。ボタンには、 $1$ から $N$ までの番号がついています。ボタン $i$ が光っているときにそのボタンを押すと、ボタン $i$ の明かりが消え、その後ボタン $a_i$ が光ります。 $i=a_i$ であることもあります。光っていないボタンを押しても、何も起こりません。

最初、ボタン $1$ が光っています。高橋君は、ボタン $2$ が光っている状態で、トレーニングをやめたいと思っています。

そのようなことは可能かどうか判定し、もし可能なら最低で何回ボタンを押す必要があるかを求めてください。

制約

$2 ≦ N ≦ 10^5$
$1 ≦ a_i ≦ N$

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $a_1$ 
 $a_2$ 
:
 $a_N$

出力

ボタン $2$ を光らせることが不可能な場合、 $-1$ を出力せよ。そうでない場合、ボタン $2$ を光らせるために必要なボタンを押す回数の最小値を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

ボタン $1,3$ の順に押せばよいです。

入力例 2Copy

Copy

出力例 2Copy

Copy

-1

ボタン $1$ を押すとボタン $3$ 、ボタン $3$ を押すとボタン $1$ が光るので、ボタン $2$ が光ることはありません。

入力例 3Copy

Copy

出力例 3Copy

Copy

Score : $200$ points

Problem Statement

Takahashi wants to gain muscle, and decides to work out at AtCoder Gym.

The exercise machine at the gym has $N$ buttons, and exactly one of the buttons is lighten up. These buttons are numbered $1$ through $N$ . When Button $i$ is lighten up and you press it, the light is turned off, and then Button $a_i$ will be lighten up. It is possible that $i=a_i$ . When Button $i$ is not lighten up, nothing will happen by pressing it.

Initially, Button $1$ is lighten up. Takahashi wants to quit pressing buttons when Button $2$ is lighten up.

Determine whether this is possible. If the answer is positive, find the minimum number of times he needs to press buttons.

Constraints

$2 ≤ N ≤ 10^5$
$1 ≤ a_i ≤ N$

Input

Input is given from Standard Input in the following format:

 $N$ 
 $a_1$ 
 $a_2$ 
:
 $a_N$

Output

Print $-1$ if it is impossible to lighten up Button $2$ . Otherwise, print the minimum number of times we need to press buttons in order to lighten up Button $2$ .

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

Press Button $1$ , then Button $3$ .

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

-1

Pressing Button $1$ lightens up Button $3$ , and vice versa, so Button $2$ will never be lighten up.

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy