G. Кольорові книги#8757

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

1 секунда

64 мегабайти

Дуже складна

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

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

Вхідні дані

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

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $1 \leq a_{i} \leq n$ 1 \leq a_i \leq n) — числа, записані на книгах.

Гарантується, що всі числа різні.

Третій рядок містить $n$ цілих чисел $c_{1}, c_{2}, \dots, c_{n}$ c_1, c_2, \ldots, c_n ( $1 \leq c_{i} \leq n$ 1 \leq c_i \leq n) — кольори книг.

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

Вихідні дані

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

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

Приклади

Приклад 1

Приклад 2

Оцінювання

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

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

$10 + ⌊ 30 - 30 \cdot (k - m) / (3 n - m)⌋$ 10 + \lfloor 30 - 30 \cdot (k - m)/(3n - m) \rfloor, якщо $m < k \leq 3 n$ m < k \leq 3n

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

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

(10 балів) $1000 < n \leq 1 0^{5}$ 1000 < n \leq 10^5, усі кольори різні.
(40 балів) без додаткових обмежень.