LCC '22 Contest 2 S1 - Skipper's Nut Hunt

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type

Skipper the squirrel has recently escaped his human owners, but being a new wild squirrel, Skipper is in dire need of nuts! Luckily for him, his mentor, Nibbles has buried nuts and maps at each of N locations. Specifically, at location i, Nibbles has hidden a nut and a map to location a_i. So, whenever Skipper is at i, he will collect the nut at that location (if he hadn't collected it before) and follow the map to location a_i, and repeat. Skipper is currently at location R. If Skipper repeats this process indefinitely, can you figure out how many nuts he collects?


1\le N\le 3\times 10^5

1\le a_i\le N

1\le R\le N

Input Specification

The first line contains two integers, N and R.

The second line contains N integers, the i-th of which corresponds to a_i

Output Specifcation

One line with one integer, the number of nuts Skipper can collect by repeating his process indefinitely

Sample Input

7 4
5 4 1 3 6 4 2

Sample Output


Sample Explanation

Skipper starts at location 4, where he collects a nut and moves to location a_4=3

At location 3, collects a nut at location 3 and moves to location a_3=1

Even if Skipper repeats this process indefinitely, he will only visit the locations 1, 3, 4, 5, and 6. Since he can only collect at most one nut at each location, Skipper can only collect 5 nuts.


There are no comments at the moment.