Teleporters

Teleporters

Time limit: 0.5 s.
Memory limit: 256 MB

There are \(N\) teleporters arranged in a row and numbered from \(1\) to \(N\). Each teleporter sends you to another teleporter.

You are given an array \(a\) of size \(N\), where \(a_i\) represents the destination of teleporter \(i\). If you enter teleporter \(i\), you will immediately be sent to teleporter \(a_i\). You can not move, you can only enter the teleporter at your current position.

You start at teleporter \(S\). Each time you use a teleporter, it counts as one step.

Determine the number of steps after which you will return to teleporter \(S\) for the first time. If it is impossible to return to \(S\), output \(-1\).

Input

The first line of input contains two integers \(N\) and \(S\) respectively. \((1 \le S \le N \le 2 \cdot 10^5)\)

The next line contains \(N\) integers \(a_1, a_2 \dots a_n\). \((1 \le a_i \le N)\)

Output

Print a single integer representing the number of steps to reach teleporter \(S\) again. If it is impossible to return to \(S\), print \(-1\).

Scoring

In this problem, each test case will be scored separately. Your score is the sum of scores for all test cases.

Examples

Input

8 3
6 1 1 3 7 5 8 3

Output

6

Input

5 4
3 4 1 3 5

Output

-1

Note

In the first example you’ll start at teleporter 3 and move the following sequence of teleporters: 3, 1, 6, 5, 7, 8 , 3. therefore we revisit telporter 3 after 6 steps.

In the second example we’ll start at teleporter 4 and move as follows: 4, 3, 1, 3. we notice that we’ll keep repeating teleporters 3 and 1. Thus, we’ll never reach teleporter 4 again.

Solution

Follow the only possible path and mark every visited teleporter. If we return to \(S\), the current number of steps is the answer. If we reach any other visited teleporter first, the path has entered a cycle that does not contain \(S\), so returning is impossible.

The complexity is \(O(N)\) time and memory.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, s;
    cin >> n >> s;

    vector<int> destination(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> destination[i];
    }

    vector<bool> visited(n + 1, false);
    int current = s;
    int steps = 0;

    while (true) {
        if (visited[current]) {
            cout << -1 << '\n';
            return 0;
        }

        visited[current] = true;
        current = destination[current];
        steps++;

        if (current == s) {
            cout << steps << '\n';
            return 0;
        }
    }
}