题目描述

今天，哥萨克·乌斯找到了一排书架。书架上一共有 $n$ 本书，排成一行。每本书上写着一个整数 $a_i$。所有这些整数互不相同，并且都在 $[1,n]$ 范围内。换句话说，$a$ 是一个排列。

此外，每本书都有一种颜色，第 $i$ 个位置上的书的颜色为 $c_i$。

哥萨克想把书架整理好，使书按照书上数字的升序排列：写着 $1$ 的书排在第一位，写着 $2$ 的书排在第二位，依此类推。

一次操作中，他可以交换任意两本颜色不同的书的位置。

请帮助乌斯用尽可能少的操作完成整理。保证一定存在解。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示书的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le n$），表示从左到右每本书上写的数字。保证这些数字互不相同。

第三行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$（$1 \le c_i \le n$），表示从左到右每本书的颜色。

保证一定存在可行方案。

输出格式

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

接下来 $k$ 行，每行输出两个整数 $x,y$，表示交换当前位置为 $x$ 和 $y$ 的两本书。

要求每次交换时，这两本书的颜色必须不同；所有操作结束后，书必须按照数字从小到大排列。

由于答案可能不唯一，本题使用 Special Judge 检验。

输入

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

评分方式

本题共有三个计分部分，外加样例测试点。

1. 最高 $50$ 分：$n \le 1000$。

   设某个测试点的最少操作次数为 $m$，你的程序使用的操作次数为 $k$。该测试点得分为：

   • 若 $k=m$，得 $50$ 分；

   • 若 $m<k\le 3n$，得

     $$10+\left\lfloor 30-30\cdot \frac{k-m}{3n-m}\right\rfloor$$

   • 若 $k>3n$，得 $0$ 分。

   该部分最终得分为该部分所有测试点得分的最小值。

2. $10$ 分：$1000<n\le 10^5$，且所有颜色互不相同。

3. $40$ 分：无额外限制。