G. Colored Books#8757
Cossack Vus discovered a shelf filled with books. There are books on this shelf, arranged in a single row. Each book has a unique integer a_i written on it, where all numbers are distinct and fall within the range . This means is a permutation of numbers from 1 to n. Additionally, each book is painted in a specific color, with the color of the -th book denoted as c_i.
Vus's goal is to rearrange the books so that they are in ascending order based on the numbers written on them. This means the book with the number should be first, followed by the book with the number , and so on. Vus can achieve this by swapping any two books that have different colors. Your task is to help Vus achieve this arrangement using the minimum number of swaps. It is guaranteed that this task is always possible.
The first line contains a single integer (1 \leq n \leq 10^5) — the total number of books.
The second line contains integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq n) — the numbers written on the books.
All numbers are distinct.
The third line contains integers c_1, c_2, \ldots, c_n (1 \leq c_i \leq n) — the colors of the books.
It is guaranteed that a solution always exists.
On the first line, output a single integer — the number of swap operations performed.
The following lines should each contain two integers — the positions of the books that were swapped.
Example 1
Example 2
(up to 50 points) n \leq 1000; let be the minimum number of operations required to sort the books in a given test, and be the number of operations you used. The score for this test will be:
, if k = m
10 + \lfloor 30 - 30 \cdot (k - m)/(3n - m) \rfloor, if m < k \leq 3n
, if k > 3n.
Your score for this block will be the minimum of the results from all tests in the block.
(10 points) 1000 < n \leq 10^5, where all colors are different.
(40 points) Without any additional constraints.