老虎和蒜头是好朋友。

老虎最近又得到了一个长度为 $ n $ 的排列。与往常不同的是，这个排列中的元素还有颜色。现在老虎想要在最少的交换次数下，将这个排列排序。注意与平常的交换不同的是，这里的交换只能交换颜色不同的数。

你需要输出一组这样的方案，满足操作次数最少。

输入格式

输入的第一行包括两个正整数 $ n $ ，表示排列的长度。

接下来的一行包括一个排列 $ p ​$ 。

接下来的一行包括一个颜色序列 $ c $。

输入保证至少存在一组解。

输出格式

输出的第一行包括一个整数 $ m $ ，表示最少的操作次数。

接下来 $ m ​$ 行，每行两个数 $ i ​$ 和 $ j ​$ ，表示交换 $ (p_i, c_i) ​$ 和 $ (p_j, c_j) ​$ ，你需要保证 $ c_i \ne c_j ​$ 。

样例一

input

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

output

5
2 4
7 4
2 7
1 2
1 5

样例二

input

2
2 1
1 2

output

1
1 2

限制与约定

本题共包括 3 个子任务，对于所有子任务，均有 $ 1 \le c_i \le n ​$ 。

Subtask 1(17 分): $ 1 \le n \le 10 $

Subtask 2(30 分): $ 1 \le n \le 1000 $

Subtask 3(53 分): $ 1 \le n \le 10^5 $

时间限制: 2s

空间限制: 512MB