Сортировка
У Айжан есть последовательность из n целых чисел S[0], S[1], ..., S[n-1]. Эта последовательность состоит из различных чисел от 0 до n - 1. Айжан пробует отсортировать эту последовательность по возрастанию, меняя местами некоторые пары элементов. Ее друг Ермек также собирается менять местами некоторые пары элементов, но нет уверенности, что он это сделает полезным путем.
Ермек и Айжан собираются изменять последовательность в несколько этапов. На каждом этапе сначала Ермек совершает обмен элементов местами, затем Айжан делает другой обмен. Точнее, тот, кто делает обмен, выбирает две корректные позиции и меняет местами элементы в этих позициях. Заметим, что две позиции не обязательно должны быть различными. В случае, когда они равны, элемент меняется сам с собой. Такое действие не изменяет последовательность.
Айжан знает, что Ермек не заботится о том, чтобы отсортировать последовательность S. Она знает какие именно позиции будет выбирать Ермек. Ермек планирует участвовать в m этапах. Этапы нумеруются от 0 до m - 1. Для всех i от 0 до m - 1 включительно, Ермек выберет позиции x[i] и y[i] в этапе с номером i.
Айжан хочет отсортировать последовательность S. Перед началом каждого этапа, если Айжан видит, что последовательность уже отсортирована в возрастающем порядке, весь процесс прекращается. Дана начальная последовательность S и позиции, которые Ермек собирается выбрать, требуется найти последовательность обменов, которые сможет использовать Айжан, чтобы отсортировать последовательность S. В некоторых подзадачахтребуется найти как можно более короткую последовательность обменов. Известно, что последовательность S можно отсортировать за m или меньшее количество этапов.
Если Айжан видит, что последовательность S отсортирована после обмена, сделанного Ермеком, то она может выбрать обмен в равных позициях (например 0 и 0). В результате последовательность S останется отсортированной после окончания этапа, и Айжан достигнет цели. Также отметим, если изначально последовательность S отсортирована, то минимальное количество этапов, необходимое для сортировки, равно 0.
Дана последовательность S, количество обменов m и последовательности позиций X и Y. Найдите последовательность обменов, которую Айжан может использовать для сортировки последовательности S.
Пример 1
Предположим что:
Начальная последовательность: S = 4, 3, 2, 1, 0.
Ермек собирается сделать шесть обменов (m = 6).
Последовательности X и Y, описывающие позиции, которые Ермек собирается выбрать, следующие: X = 0, 1, 2, 3, 0, 1 и Y = 1, 2, 3, 4, 1, 2. То есть, пары позиций, которые Ермек планирует выбрать, будут (0, 1), (1, 2), (2, 3), (3, 4), (0, 1) и (1, 2).
В этом случае Айжан может преобразовать последовательность S к виду 0, 1, 2, 3, 4 за три этапа. Она может сделать это, выбрав позиции (0, 4), (1, 3) и затем (3, 4). Следующая таблица отражает, как Ермек и Айжан изменяют последовательность S.
Пример 2
Предположим что:
Начальная последовательность: S = 3, 0, 4, 2, 1.
Ермек собирается сделать пять обменов (m = 5).
Пары позиций, которые Ермек планирует выбрать: (1, 1), (4, 0), (2, 3), (1, 4) и (0, 4).
В этом случае Айжан может отсортировать последовательность S за три этапа, например, выбрав пары позиций (1, 4), (4, 2) и затем (2, 2). Следующая таблица отражает, как Ермек и Айжан изменяют последовательность S.
Входные данные
Первая строка содержит длину последовательности S. Вторая строка содержит начальную последовательность S[0], S[1], ..., S[n-1] (n ≤ 200000). Следующая строка содержит количество обменов m (m ≤ 3 * n), запланированных Ермеком. Каждая из следующих m строк содержит пару чисел x[i] и y[i]. Они означают, что на i-ом (0 ≤ i ≤ m - 1) этапе Ермек планирует поменять элементы в позициях x[i] и y[i].
Выходные данные
В первой строке вывести количество обменов R Айжан. В следующих R строках вывести саму последовательность обменов минимальной длины, которую Айжан может использовать для сортировки S. В каждой строке следует выводить пару позиций для обмена p[i] и q[i].