Cloning a Random Pointer Linked List

You are given a linked list in which each node contains an integer data, a next pointer to the next node, and a random pointer which can point to any node in the list (or be null). Your task is to write a function that creates a deep copy of the linked list such that the new list has exactly the same structure as the original list.

The input is provided for multiple test cases. For each test case, the linked list is represented in a serialized format:

• The first line contains an integer n indicating the number of nodes in the list. If n = 0, the list is empty.
• If n > 0, the second line contains n integers denoting the node values in order. The next pointers are implicitly defined such that node i is connected to node i+1 for 0 ≤ i < n-1.
• The third line contains n integers, where each integer is the index (0-indexed) of the node to which the random pointer of the corresponding node points. A value of -1 indicates that the random pointer is null.

Your function cloneLinkedList should clone the list and the output should be in the same serialized format as the input for each test case. That is, for each test case, print:

1. The integer n (the number of nodes in the cloned list).
2. A line with the node values separated by single spaces.
3. A line with the random pointer indices separated by single spaces.

Note: You must read from standard input (stdin) and output to standard output (stdout).

inputFormat

The input begins with an integer T denoting the number of test cases. For each test case:

1. First line contains a single integer n representing the number of nodes in the linked list. (If n is 0, the list is empty.)
2. If n > 0, the next line contains n integers separated by spaces, representing the node values.
3. The following line contains n integers separated by spaces, each representing the index (0-indexed) of the node that the random pointer points to, or -1 if it is null.

Input is read from stdin.

outputFormat

For each test case, output the cloned linked list in the same serialized format:

1. Print the integer n (number of nodes in the cloned list).
2. Print a line of n node values separated by spaces.
3. Print a line of n integers representing the random pointer indices (using 0-indexing, and -1 for null).

Output the result to stdout.

## sample

3
0
1
10
-1
3
1 2 3
-1 0 1

0
1
10
-1
3
1 2 3
-1 0 1

</p>