Кольорові книги

Сьогодні Козак Вус знайшов поличку книг. Усього на поличці було $n$ книг, розташованих у ряд. На кожній книзі було написане одне ціле число $a_i$. Усі ці числа різні з проміжку $[1,n]$. Іншими словами, $a$ "— перестановка. Також кожна книга має свій колір, колір $i$-ої книги $c_i$.

Козак хоче навести лад на поличці, для цього потрібно, щоб книги йшли в порядку зростання чисел, записаних на них, тобто книга $1$ іде першою, наступна $2$ і так далі. За одну операцію він може поміняти місцями будь-які дві книги різного кольору. Допоможіть Вусу впоратись з цією задачею за мінімальну кількість операцій. Гарантується, що це можливо зробити.

Вхідні дані

Перший рядок містить одне ціле число $n$ ($1\le n\le 10^5$) "— кількість книг.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le n$) "— числа, записані на книгах. Гарантується, що всі числа різні.

Третій рядок містить $n$ цілих чисел $c_1,c_2,\dots ,c_n$ ($1\le c_i\le n$) "— кольори книг.

Гарантується, що рішення завжди існує.

Вихідні дані

У першому рядку виведіть одне число $k$ "— кількість операцій.

У наступних $k$ рядках виведіть по два цілі числа "— позиції книг, які потрібно поміняти місцями.

Приклади

Оцінювання

1. (до $50$ балів) $n\le 1000$; припустимо, що $m$ "— мінімальна кількість операцій, які потрібно зробити, щоб відсортувати книги в певному тесті, а $k$ "— кількість операцій, які ви використали. Тоді результат за цей тест буде рівний:

   • $50$, якщо $k=m$

   • $10+\lfloor 30-30\cdot \frac{k-m}{3n-m}\rfloor$, якщо $m<k\le 3n$

   • $0$, якщо $k>3n$.

   Ваша кількість балів за цей блок буде рівною мінімуму з результатів у всіх тестах з блоку.

2. ($10$ балів) $1000<n\le 10^5$, усі кольори різні.

3. ($40$ балів) без додаткових обмежень.