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

Обмеження: 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_{-}]\).