Сортування дисків#10883

Сортування дисків

1 секунда

128 мегабайтів

Дуже легка

Маємо $n + 1$ n + 1 стрижнів і $3 n$ дисків. Спочатку кожен з перших $n$ стрижнів містить рівно $3$ диски. Кожен диск має один з $n$ кольорів, позначених номерами від $1$ до $n$ . При цьому є рівно $3$ диски кожного з $n$ кольорів. Стрижень номер $n + 1$ n + 1 порожній.

На кожному кроці ми можемо вибрати два стрижні $a$ і $b (a \neq = b)$ b~(a \ne b) так, щоб $a$ мав як мінімум $1$ диск і $b$ мав не більше $2$ дисків, і перемістити верхній диск зі стрижня $a$ на вершину стрижня $b$ . Зверніть увагу, що жоден стрижень не може містити більше $3$ дисків одночасно.

Ваша мета — відсортувати диски. Зокрема, ви повинні виконати ряд операцій (потенційно $0$ ), щоб в кінці кожен з перших $n$ стрижнів містив рівно $3$ диски одного кольору, а $(n + 1)$ (n + 1)-ий стрижень був порожнім.

Знайдіть рішення для сортування дисків максимум за $6 n$ операцій. Можна довести, що за цієї умови рішення завжди існує. Якщо існує декілька рішень, виведіть будь-яке.

Вхідні дані

Перший рядок містить натуральне число $n (1 \leq n \leq 1000)$ n~(1 \le n \le 1000). Кожен з наступних $3$ рядків містить $n$ натуральних чисел $c_{i, j} (1 \leq i \leq 3, 1 \leq j \leq n, 1 \leq c_{i, j} \leq n)$ c_{i,j}~(1 \le i \le 3, 1 \le j \le n, 1 \le c_{i,j} \le n) — колір кожного диска, спочатку розміщеного на стрижнях. Перший з $3$ рядків вказує на верхній рядок дисків, другий рядок вказує на середній рядок, а третій рядок вказує на нижній рядок.

Вихідні дані

Перший рядок повинен містити невід'ємне ціле число $k (0 \leq k \leq 6 n)$ k~(0 \le k \le 6n) — кількість операцій. Кожен з наступних $k$ рядків повинен містити два різних числа $a_{i}, b_{i} (1 \leq a_{i}, b_{i} \leq n + 1$ a_i, b_i~(1 \le a_i, b_i \le n + 1, для всіх $1 \leq i \leq k)$ 1 \le i \le k), що представляють $i$ -у операцію (як написано в умові).

Приклади

Приклад 1

Приклад 2