Description

Procat(破貓), AKA God of cycling is planning for a trip. As a student in the CS department, he decided to use a linked list to represent his trip. However, he accidentally pointed the last node to the body of the linked list, making some of the linked lists contain a cycle. Help him find out if there is a cycle in a given linked list.

Procat plans to visit \(N\) viewpoints. Numbered from \(0\) to \(N-1\). He will start from viewpoint \(0\) and visit viewpoint \(c_i\) after visiting viewpoint \(i\), until \(c_i = -1\). Each viewpoint contains a value \(a_i\).

• Definition for singly linked list:

  typedef struct ListNode {
      int val;
      struct ListNode *next;
  } ListNode;

• This is a partial judge problem. Input and output are handled by 14210.c. All you have to do is implement the function
  bool hasCycle(ListNode *head), which returns true if there is a cycle in the given linked list, otherwise returns false.

• You should not modify the given linked list, or you will get a wrong answer.

Input

There are multiple subtasks in each testcase. The first line of the input contains an integer \(T\) indicating the number of subtasks. For each subtask, there will be three lines, formatted as following:

• One integer \(N\) indicating the number of nodes.
• \(N\) integers \(c_i\) indicating the next node of node \(i\).
• \(N\) integers \(a_i\) indicating the val stored in node \(i\).

\(N\)
\(c_0 \quad c_1 \quad c_2 \quad \ldots \quad c_{N-1}\)
\(a_0 \quad a_1 \quad a_2 \quad \ldots \quad a_{N-1}\)

It’s guaranteed that all nodes can be reached from node 0 in each testcase.

subtask 1:

subtask 2:

subtask 3:

Constraints

\(1 \le T \le 10^4\)
\(1 \le N \le 10^7\)
\(1 \le \sum N \le 10^7\)
\(-1 \le c_i < N\)
\(-10^9 \le a_i \le 10^9\)

• For \(33\%\) of the testcases, \(a\) is unique for each node.
• For \(67\%\) of the testcases, there is no additional constraint.

Output

For each subtask, output one line containing “Yes” if there is a cycle in the given linked list, otherwise output “No”. Print a newline character after each line.

Since this is a partial judge problem, you don’t have to worry about the output format.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14210.c

Partial Judge Header

14210.h

Tags

Discuss