print941. Самая умная сортировка

printСамая умная сортировка

Ограничения: время – 5s/10s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Парламент уже давно вынашивал планы по созданию и законодательному закреплению "умной сортировки", ограничивающей ненужные перестановки в стране. Нашему корреспонденту удалось увидеть часть наброска к законопроекту:
Есть массив из `N` чисел – `1,\ 2,\ 3,\ …,\ N`. Потом некоторые его элементы переставляются. Нужно найти последовательность перестановок, которая все элементы вернет на место. Причем, делать перестановку `A_i\ ↔\ A_j` можно только один раз.
Перестановки `A_i\ ↔\ A_j` и `A_j\ ↔\ A_i` являются одной и той же перестановкой, так что если использована перестановка `A_i\ ↔\ A_j`, то `A_j\ ↔\ A_i` использовать уже нельзя.
Что ж. Похоже, о целесообразности подобных изысканий остается только догадываться. Ну а проверку разумности и возможности осуществления таких сортировочных действий мы оставляем читателю.
Ввод
Первая строка – число `N` (количество чисел в массиве), где `N\ ≤\ 6`.
Последующие строки до конца файла – пары позиций `(i,\ j)` в массиве, элементы в которых переставляются (происходит обмен `A_i\ ↔\ A_j`).
Вывод
Последовательность пар позиций `(i,\ j)`, которая вернет все на место. Каждая пара должна быть использована не больше одного раза, и те пары, которые были во входном файле, использовать нельзя. Если такой последовательности не существует, то вывести одно число 0. Если таких последовательностей несколько, то вывести любую из них.

Пример ввода 1

4
1 2
3 4
2 3

Пример вывода 1

1 4
1 3
2 4

Пример ввода 2

2
1 2

Пример вывода 2

0

Пример ввода 3

6
1 6
2 5
3 4

Пример вывода 3

1 2
1 3
1 4
2 3
2 4
5 6
1 5
2 6
3 5
4 5
4 6
Источник: Турнир "Экспонента-2008"
loading