K-th Node in Cycle
You are given an array next of size N, where next[i] is the index of the next element to visit from index i. The array represents a linked structure which may contain a cycle. Find the index of the node that is exactly K steps away from the starting node (index 0), following the next pointers. If the path goes into a cycle and K is large enough to revisit nodes, you should still find the node that is K steps away from index 0.
Input
The first line contains two integers N and K. The second line contains N integers representing the array next.
Output
Print a single integer, the index of the node that is K steps away from index 0.
Constraints
1 <= N <= 200000, 0 <= K <= 10^18, 0 <= next[i] < N for all i.
Example 1
5 10 1 2 3 4 0
0
N=5, K=10. Path: 0 -> 1 -> 2 -> 3 -> 4 -> 0 (cycle). 10 steps from 0 lands on node 0.
Example 2
7 15 1 2 3 4 5 6 2
5
N=7, K=15. Path: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 2 (cycle start at 2). 15 steps from 0 lands on node 4.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 10 1 2 3 4 0
7 15 1 2 3 4 5 6 2