环形链表 II

题目描述

给定一个链表，请判断链表中是否存在环。如果存在，输出环开始的第一个节点在原链表中的下标；如果不存在，输出 -1。

本题使用整数 pos 表示链表尾部连接到链表中的位置（下标从 0 开始）：

• 如果 pos = -1，表示链表中没有环；
• 否则表示链表尾节点的 next 指向下标为 pos 的节点。

你需要根据给定的链表和 pos，求出环开始的第一个节点的下标。

输入格式

第一行输入两个整数 n 和 pos，分别表示链表长度以及尾节点连接的位置。

第二行输入 n 个整数，表示链表节点值。

输出格式

输出一个整数：

• 若存在环，输出环开始节点的下标；
• 若不存在环，输出 -1。

数据范围

1 <= n <= 10^5

-10^9 <= val <= 10^9

-1 <= pos < n

样例 1

输入

4 1
3 2 0 -4

输出

1

样例 2

输入

2 0
1 2

输出

0