Find Duplicate Node in Path
You are given an array next_nodes of size N, where next_nodes[i] is the index of the next node visited from node i. Node indices range from 0 to N-1. The sequence of visited nodes starts at index 0. This sequence may eventually enter a cycle. Your task is to find the index of the first node that is visited more than once. If no node is visited more than once, output -1. Node 0 is always the starting node.
Input
The first line contains an integer N (1 <= N <= 200000). The second line contains N integers, next_nodes[0], next_nodes[1], ..., next_nodes[N-1] (-1 <= next_nodes[i] < N). A value of -1 indicates no next node (which is only possible if N=1 and next_nodes[0]=-1). If N > 1, every node must have a next node index within [0, N-1].
Output
Print a single integer: the index of the first node that appears twice in the path starting from node 0. If no node is repeated, print -1.
Constraints
1 <= N <= 200000. -1 <= next_nodes[i] < N. If N > 1, next_nodes[i] is in [0, N-1] for all i.
Example 1
5 1 2 3 4 2
2
Path: 0 -> 1 -> 2 -> 3 -> 4 -> 2. Node 2 is the first repeated node.
Example 2
3 1 2 0
0
Path: 0 -> 1 -> 2 -> 0. Node 0 is the first repeated node.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 2 3 4 2
3 1 2 0