Олимпиады по программированию

olympiads.ru

II Всероссийская заочная олимпиада школьников по информатике, 2007/08 учебный год

Задача I. Игра с обменами (OFF-LINE проверка)

Вася и Петя играют в увлекательную игру. Вася выписал подряд числа от 1 до N. А Петя выписал P пар чисел (A_i, B_i).

Теперь Вася преобразует имеющуюся последовательность чисел - он меняет местами числа в этой последовательности. Если некоторая пара чисел (A_i, B_i) выписана Петей, то Вася имеет право в любой момент взять числа из последовательности, стоящие на местах A_i и B_i и поменять их местами.

Например, если N=5. Тогда изначально Васей выписана последовательность
1 2 3 4 5

Пусть Петя написал две пары чисел: (1,2) и (2,5). Тогда Вася в любой момент может менять числа, стоящие на 1 и 2 местах, или же числа, стоящие на 2 и 5 местах.

Например, он может последовательно получить следующие последовательности:
2 1 3 4 5 (поменяв числа на 1 и 2 местах)
2 5 3 4 1 (поменяв числа на 2 и 5 местах)
5 2 3 4 1 (поменяв числа на 1 и 2 местах).

Пете не показываются промежуточные последовательности, а выписывается лишь полученная на последнем шаге.

От Пети требуется проверить, мог ли Вася получить такую последовательность не нарушая правил игры, и если мог, то указать, в результате какой последовательности обменов (при этом не требуется, чтобы число обменов было минимально возможным).

Напишите программу, которая поможет Пете справиться с этой задачей.

Формат входных данных

Сначала записано число N (1≤N≤100) - количество чисел в последовательности. Дальше идет N чисел - последовательность, полученная Васей (в последовательности каждое из чисел от 1 до N встречается ровно один раз).

Далее идет число P (0≤P≤10000) - количество пар чисел, выписанных Петей. Далее записано P пар чисел (каждое число пары - из диапазона от 1 до N).

Формат выходных данных

В первую строку выходного файла выведите сообщение YES (если такая последовательность могла быть честно получена Васей) и NO (если такую последовательность Вася не мог получить, не нарушая правил игры).

В случае, если такая последовательность могла быть получена, далее выведите способ ее получения (если вариантов несколько, выведите любой из них). Сначала выведите число K - количество операций обмена (оно не должно превышать 100000), а затем K пар чисел, задающих номера мест, на которых стоят обмениваемые элементы (числа в паре могут быть выданы в любом порядке). Гарантируется, что если решение существует, то существует решение с числом обменов, не превышающим 100000.

Примеры

5
5 2 3 4 1
2
1 2
2 5

YES
3
1 2
2 5
2 1 

5
2 3 4 5 1
2
1 2
2 5

NO