Сортування#7770

Сортування

1 секунда

128 мегабайтів

Дуже легка

У Айжан є послідовність із $n$ цілих чисел $S_{0}, S_{1}, ..., S_{n - 1}$ S_0, S_1, ..., S_{n-1}. Ця послідовність складається з різних чисел від $0$ до $n - 1$ n - 1. Айжан намагається відсортувати її за зростанням, міняючи місцями деякі пари елементів. Її друг Єрмек також збирається виконувати обміни елементів, однак немає гарантії, що його дії будуть корисними.

Єрмек і Айжан змінюють послідовність поетапно. На кожному етапі спочатку Єрмек виконує обмін, потім Айжан виконує свій обмін. Точніше, учасник, який виконує обмін, вибирає дві допустимі позиції і міняє місцями елементи в цих позиціях. Зауважимо, що вибрані позиції не обов'язково мають бути різними. Якщо вони збігаються, елемент міняється сам із собою, і послідовність залишається незмінною.

Айжан знає, що Єрмек не прагне відсортувати послідовність $S$ , і їй заздалегідь відомі позиції, які він буде вибирати. Єрмек планує виконати $m$ етапів. Етапи нумеруються від $0$ до $m - 1$ m - 1. Для кожного $i$ від $0$ до $m - 1$ m - 1 включно Єрмек вибирає позиції $x_{i}$ x_i та $y_{i}$ y_i на етапі з номером $i$ .

Айжан хоче відсортувати послідовність $S$ . Перед початком кожного етапу, якщо послідовність вже відсортована за зростанням, процес негайно припиняється. Дано початкову послідовність $S$ і позиції, які буде вибирати Єрмек. Потрібно знайти послідовність обмінів, яку може використовувати Айжан, щоб відсортувати $S$ . У деяких підзадачах необхідно знайти якомога коротшу послідовність обмінів. Гарантується, що послідовність $S$ можна відсортувати за $m$ або меншу кількість етапів.

Якщо після обміну Єрмека послідовність $S$ вже відсортована, Айжан може вибрати обмін однакових позицій (наприклад, $0$ і $0$ ). Тоді послідовність залишиться відсортованою до кінця етапу, і мету буде досягнуто. Також зауважимо, що якщо послідовність $S$ спочатку відсортована, то мінімальна кількість етапів дорівнює $0$ .

Дано послідовність $S$ , кількість етапів $m$ і послідовності позицій $X$ та $Y$ . Знайдіть послідовність обмінів, яку Айжан може використовувати для сортування послідовності $S$ .

Вхідні дані

Перший рядок містить довжину послідовності $S$ .

Другий рядок містить початкову послідовність $S_{0}, S_{1}, ..., S_{n - 1} (n \leq 200000)$ S_0, S_1, ..., S_{n-1}~(n \le 200000).

Наступний рядок містить кількість етапів $m (m \leq 3 \cdot n)$ m~(m \le 3 \cdot n), запланованих Єрмеком.

Кожен із наступних $m$ рядків містить пару чисел $x_{i}$ x_i та $y_{i}$ y_i. Вони означають, що на етапі $i$ $(0 \leq i \leq m - 1)$ (0 \le i \le m - 1) Єрмек планує поміняти елементи в позиціях $x_{i}$ x_i та $y_{i}$ y_i.

Вихідні дані

У першому рядку виведіть кількість обмінів $R$ , виконаних Айжан.

У наступних $R$ рядках виведіть послідовність обмінів мінімальної довжини, яку Айжан може використовувати для сортування $S$ .

У кожному рядку слід вивести пару позицій $p_{i}$ p_i та $q_{i}$ q_i для обміну.

Приклади

Приклад 1. Припустимо, що:

Початкова послідовність: $S = 4, 3, 2, 1, 0$ S = 4, 3, 2, 1, 0.
Єрмек збирається виконати шість обмінів $(m = 6)$ (m = 6).
Послідовності $X$ та $Y$ , що задають позиції, які буде вибирати Єрмек: $X = 0, 1, 2, 3, 0, 1$ X = 0, 1, 2, 3, 0, 1 і $Y = 1, 2, 3, 4, 1, 2$ Y = 1, 2, 3, 4, 1, 2. Тобто пари позицій: $(0, 1), (1, 2), (2, 3), (3, 4), (0, 1)$ (0, 1), (1, 2), (2, 3), (3, 4), (0, 1) і $(1, 2)$ .

У цьому випадку Айжан може перетворити послідовність $S$ на $0, 1, 2, 3, 4$ 0, 1, 2, 3, 4 за три етапи. Наприклад, вибравши пари $(0, 4), (1, 3)$ (0, 4), (1, 3) і потім $(3, 4)$ . Наступна таблиця показує, як Єрмек і Айжан змінюють послідовність $S$ .

Приклад 2. Припустимо, що:

Початкова послідовність: $S = 3, 0, 4, 2, 1$ S = 3, 0, 4, 2, 1.
Єрмек збирається виконати п'ять обмінів $(m = 5)$ (m = 5).
Пари позицій, які буде вибирати Єрмек: $(1, 1), (4, 0), (2, 3), (1, 4)$ (1, 1), (4, 0), (2, 3), (1, 4) і $(0, 4)$ .

У цьому випадку Айжан може відсортувати послідовність $S$ за три етапи, наприклад, вибравши пари $(1, 4), (4, 2)$ (1, 4), (4, 2) і потім $(2, 2)$ . Наступна таблиця показує, як Єрмек і Айжан змінюють послідовність $S$ .

Приклад 1

Приклад 2