Circular Dependency Detector

Time Limit: 2sMemory: 256MB

Problem

A risk management system models dependencies between financial instruments as a linked list. Each instrument points to the next one in the chain. However, a faulty configuration might create a circular dependency where the chain loops back to a previous instrument.

Given a linked list, determine whether it contains a cycle.

Input Format

Space-separated integers. All values except the last are node values. The last integer is the cycle position (0-indexed) — the index the tail node connects to. Use -1 if there is no cycle.

Output Format

Print true if a cycle exists, false otherwise.

Examples

Example 1

Input

3 2 0 -4 1

Output

true

List is [3,2,0,-4] with tail connecting to index 1 (value 2). The cycle is 2->0->-4->2.

Example 2

Input

1 -1

Output

false

Single node with no cycle (cycle position -1 means no cycle).

Constraints

•0 ≤ list length ≤ 10^4
•-10^5 ≤ node value ≤ 10^5
•Cycle position -1 means no cycle; otherwise it's the 0-indexed position the tail connects to

Loading interactive editor…