Clone a Linked List with Random Pointers

You are given a linked list in which each node has an additional random pointer which could point to any node in the list or be null. Your task is to create a deep copy of the list. The original list should remain unchanged and the copied list should contain new nodes with the same values and pointers (both next and random) as in the original list.

The linked list is provided in a serialized format. The first line contains an integer n, representing the number of nodes. The following n lines each contain two integers. The first integer is the index of the next node (or -1 if there is no next node) and the second integer is the index of the random pointer (or -1 if null). The nodes are created with values 1 through n in order.

Your program should read the input from standard input (stdin), clone the linked list, and then output the serialized format of the cloned list to standard output (stdout). The output format should be exactly as the input format: first output the number of nodes in the cloned list, then for each node output a line containing two integers representing the next pointer index and the random pointer index (using -1 for null pointers).

All indices are 0-indexed, and if a node pointer is specified as -1 it means that pointer is null.

The cloning algorithm should run in O(n) time and use O(1) extra space (not counting the space for the new nodes).

inputFormat

The first line contains an integer n (n ≥ 0) — the number of nodes in the linked list. Each of the next n lines contains two space-separated integers: the first integer is the index of the next node and the second integer is the index of the random node. Use -1 to represent null.

It is guaranteed that if the next index is not -1, it will be a valid index (0-indexed) within the list, and similarly for the random index.

outputFormat

Output the cloned linked list in the same serialized format. The first line should contain the number of nodes in the cloned list, followed by n lines each with two space-separated integers: the index of the next pointer and the index of the random pointer for that node (use -1 for null).

## sample

3
1 2
2 0
-1 1

3
1 2
2 0
-1 1

</p>