SDE Path

Find the Starting Point of a Cycle

Medium

Find the Starting Point of a Cycle

Given a linked list with a cycle, find the node where the cycle begins.

Input format

The first line contains N and POS — the 0-based index the last node links back to (a cycle always exists). The second line contains the N node values. The judge builds the cycle; solve it by traversing the list only.

Output format

Print the 0-based index (distance from head) of the node where the cycle begins.

Constraints

  • Values fit in a 64-bit signed integer
  • Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

Sample cases

Example 1
Input
4 1
3 2 0 -4
Expected output
1
Example 2
Input
1 0
7
Expected output
0