Detect Circular Linked List

You are given a singly linked list. Your task is to determine whether the linked list contains a cycle (i.e. it is circular) or not.

A linked list is defined as circular if there exists a node in the list that can be reached again by continuously following the next pointer. Otherwise, it is non-circular.

You can use the well-known Floyd's Cycle Detection algorithm (also known as the tortoise and the hare algorithm), which employs two pointers moving at different speeds. In particular, if we denote the positions of the two pointers by \( slow \) and \( fast \), then if at any time \( slow = fast \) (except at the start), the list is circular. Otherwise, if the fast pointer reaches the end of the list, the list is not circular.

For a quick reminder, the recurrence in Floyd's algorithm can be summarized by:
\[ slow = slow.next, \quad fast = fast.next.next \]

inputFormat

The input consists of multiple test cases. The first line contains a single integer T, the number of test cases. The description of each test case follows:

• The first line contains an integer N denoting the number of nodes in the linked list.
• The second line contains N space-separated integers representing the node values.
• The third line contains an integer representing the circular index k (0-indexed). If k = -1, then the list does not have a cycle; otherwise, the next pointer of the last node points to the k-th node, thereby forming a cycle.

Please read from standard input (stdin).

outputFormat

For each test case, output a single line to standard output (stdout):

• Print CIRCULAR if the linked list contains a cycle.
• Print NOT CIRCULAR if the linked list does not contain a cycle.

## sample

4
3
1 2 3
-1
4
10 20 30 40
1
1
5
-1
2
1 2
0

NOT CIRCULAR
CIRCULAR
NOT CIRCULAR
CIRCULAR

</p>