Дві перестановки кульок

Обмеження: 2 сек., 256 МіБ

Зеник любить грати з різнокольоровими кульками.

В нього є 2 рядки кульок. В кожному рядку по $n$ кульок, на яких написано числа між 1 та $n$ так, що числа у кожному рядку утворюють перестановку. В першому рядку всі кульки сині, в другому жовті.

За 1 хід можна вибрати одну кульку в першому рядку, одну кульку в другому рядку та поміняти їх місцями. Допоможіть Зенику за не більше ніж $n + 1$ хід отримати ситуацію в якій:

• в першому рядку всі кульки сині

• в другому рядку всі кульки жовті

• перестановки на кульках в першому і другому рядку однакові

Вхідні дані

В першому рядку задано одне ціле число $n$ — кількість кульок в кожному з рядків.

У другому рядку задано $n$ натуральних чисел $p_1, p_2, \ldots, p_n$ — перестановка синіх кульок.

У третьому рядку задано $n$ натуральних чисел $q_1, q_2, \ldots, q_n$ — перестановка жовтих кульок.

Вихідні дані

В першому рядку виведіть одне число $k$ — кількість ходів, яку ви хочете зробити. В кожному з наступних $k$ рядків виведіть два числа $a_i$ та $b_i$, які означатимуть зміну місцями кульки на позиції $a_i$ в першому рядку і кульки на позиції $b_i$ в другому рядку. $k$ не повинно перевищувати $n + 1$.

Гарантується, що при заданих обмеженнях відповідь завжди існує. Якщо існує декілька можливих послідовностей ходів, виведіть будь-яку.

Обмеження

$1 \le n \le 2 \cdot 10^{5}$,

$1 \le p_i, q_i \le n$,

Масиви $[p_1, p_2, \ldots, p_n]$ і $[q_1, q_2, \ldots, q_n]$ є перестановками.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
6 2 3 4 1 6 5 6 3 1 2 4 5	7 3 4 5 4 4 4 3 4 1 1 1 4 1 1

Примітки

Пояснення до прикладу (символи + та - відповідають синім та жовтим кулькам):

• Вхідні перестановки: $[2_{+} \quad 3_{+} \quad 4_{+} \quad 1_{+} \quad 6_{+} \quad 5_{+}]$ та $[6_{-} \quad 3_{-} \quad 1_{-} \quad 2_{-} \quad 4_{-} \quad 5_{-}]$;

• Хід 1 $a_1 = 3, b_1 = 4$: $[2_{+} \quad 3_{+} \quad 2_{-} \quad 1_{+} \quad 6_{+} \quad 5_{+}]$ та $[6_{-} \quad 3_{-} \quad 1_{-} \quad 4_{+} \quad 4_{-} \quad 5_{-}]$;

• Хід 2 $a_2 = 5, b_2 = 4$: $[2_{+} \quad 3_{+} \quad 2_{-} \quad 1_{+} \quad 4_{+} \quad 5_{+}]$ та $[6_{-} \quad 3_{-} \quad 1_{-} \quad 6_{+} \quad 4_{-} \quad 5_{-}]$;

• Хід 3 $a_3 = 4, b_3 = 4$: $[2_{+} \quad 3_{+} \quad 2_{-} \quad 6_{+} \quad 4_{+} \quad 5_{+}]$ та $[6_{-} \quad 3_{-} \quad 1_{-} \quad 1_{+} \quad 4_{-} \quad 5_{-}]$;

• Хід 4 $a_4 = 3, b_4 = 4$: $[2_{+} \quad 3_{+} \quad 1_{+} \quad 6_{+} \quad 4_{+} \quad 5_{+}]$ та $[6_{-} \quad 3_{-} \quad 1_{-} \quad 2_{-} \quad 4_{-} \quad 5_{-}]$;

• Хід 5 $a_5 = 1, b_5 = 1$: $[6_{-} \quad 3_{+} \quad 1_{+} \quad 6_{+} \quad 4_{+} \quad 5_{+}]$ та $[2_{+} \quad 3_{-} \quad 1_{-} \quad 2_{-} \quad 4_{-} \quad 5_{-}]$;

• Хід 6 $a_6 = 1, b_6 = 4$: $[2_{-} \quad 3_{+} \quad 1_{+} \quad 6_{+} \quad 4_{+} \quad 5_{+}]$ та $[2_{+} \quad 3_{-} \quad 1_{-} \quad 6_{-} \quad 4_{-} \quad 5_{-}]$;

• Хід 7 $a_7 = 1, b_7 = 1$: $[2_{+} \quad 3_{+} \quad 1_{+} \quad 6_{+} \quad 4_{+} \quad 5_{+}]$ та $[2_{-} \quad 3_{-} \quad 1_{-} \quad 6_{-} \quad 4_{-} \quad 5_{-}]$.