题目描述

题目译自 Ukrainian Olympiads in Informatics 2019 Stage 4 Day2 T3. Кольорові книги

今天，科扎克·武斯发现了一个书架。书架上总共有 $n$ 本书，排成一排。每本书上写有一个整数 $a_i$。这些数字是 $[1, n]$ 区间内的不同整数，换句话说，$a$ 是一个排列。同时，每本书有一个颜色，第 $i$ 本书的颜色为 $c_i$。

科扎克想要整理书架，使书籍按书上数字的升序排列，即数字为 $1$ 的书排在第一位，接下来是 $2$，以此类推。一次操作中，他可以交换任意两本不同颜色的书的位置。请帮助武斯以最少的操作次数完成这个任务。保证任务一定有解。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 10^{5})$，表示书的总数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq n)$，表示每本书上写的数字。保证所有数字两两不同。

第三行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$ $(1 \leq c_i \leq n)$，表示每本书的颜色。

保证总是存在解。

输出格式

第一行输出一个数字 $k$，表示操作次数。

接下来的 $k$ 行，每行输出两个整数，表示需要交换位置的两本书的编号。

7
2 5 3 7 1 6 4
3 2 2 3 3 2 3

5
2 4
7 4
2 7
1 2
1 5

2
2 1
1 2

1
1 2

数据范围与提示

详细子任务附加限制及分值如下表所示：

对于子任务 $1$，设 $m$ 为某个测试点中排序书籍所需的最小操作次数，$k$ 为你使用的操作次数，则该测试点得分为：

• 若 $k = m$，得 $50$ 分；
• 若 $m < k \leq 3n$，得 $10 + \lfloor 30 - 30 \cdot \frac{k-m}{3n-m} \rfloor$ 分；
• 若 $k > 3n$，得 $0$ 分。