题目描述

Pesho 面前有一个书架，书架上从左到右一排放着 N 本书，位置编号为 1 到 N。

每本书上写有一个正整数 a_i（其中 i 表示这本书当前所在的位置），并且不同书上的数字互不相同。换句话说，按当前摆放顺序看去，这些数字构成了 1 到 N 的一个排列。每本书还被染成某种颜色，位于位置 i 的书的颜色记为 c_i。

Pesho 想把这些书整理成如下顺序：编号为 i 的位置上，放置写着数字 i 的那本书。

为此，他可以依次执行若干操作。一次操作中，他可以交换两本颜色不同的书的位置。

请编写程序 books，求出使书架整理成目标顺序所需的最少操作次数，并给出一种可行的操作序列。

保证初始排列一定存在解。

输入格式

第一行输入一个整数 N，表示书的数量。

第二行输入 N 个正整数，表示当前从左到右每本书上写的数字。保证这些数字构成 1 到 N 的一个排列。

第三行输入 N 个正整数 c_1, c_2, ..., c_N，表示当前从左到右每本书的颜色。

输出格式

第一行输出一个整数 K，表示所求的最少操作次数。

接下来 K 行，每行输出两个正整数，表示这一操作中需要交换的两本书所在的位置编号。

数据范围

• 1 ≤ N ≤ 10^5
• 1 ≤ c_i ≤ N

样例 1

输入

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
2 1
1 2

输出

1
1 2

子任务与评分

子任务 1（50 分）

N ≤ 1000。设真正所需的最少操作数为 M，你的程序输出的最少操作数为 K。则对单个测试点的得分规则为：

• 若 K = M，得 50 分；
• 若 M < K ≤ 3N，得分为

$$10 + \left\lfloor 30 - 30 \cdot \frac{K - M}{3N - M} \right\rfloor$$

• 若 K > 3N，得 0 分。

该子任务的得分为该子任务中所有测试点所得分数的最小值。

子任务 2（10 分）

• 1000 < N ≤ 10^5
• 所有书的颜色两两不同

子任务 3（40 分）

无额外限制。

子任务 2 和子任务 3 的分数只有在对应子任务的所有测试点全部通过时才能获得。