G. Colored Books

Cossack Vus discovered a shelf filled with books. There are n 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 [1; n]. This means a is a permutation of numbers from 1 to n. Additionally, each book is painted in a specific color, with the color of the i-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 1 should be first, followed by the book with the number 2, 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.

Input Format:

• The first line contains a single integer n (1 ≤ n ≤ 10^5) — the total number of books.

• The second line contains n integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n) — the numbers written on the books. All numbers are distinct.

• The third line contains n integers c[1], c[2], ..., c[n] (1 ≤ c[i] ≤ n) — the colors of the books.

It is guaranteed that a solution always exists.

Output Format:

• On the first line, output a single integer k — the number of swap operations performed.

• The following k lines should each contain two integers — the positions of the books that were swapped.

Scoring:

1. (up to 50 points) For n ≤ 1,000, let m be the minimum number of operations required to sort the books in a given test, and k be the number of operations you used. The score for this test will be:

   • 50, if k = m

   • 10 + ⌊30 - 30 * (k - m)/(3n - m)⌋, if m < k ≤ 3n

   • 0, if k > 3n

   Your score for this block will be the minimum of the results from all tests in the block.

2. (10 points) For 1,000 < n ≤ 10^5, where all colors are different.

3. (40 points) Without any additional constraints.

Examples