Лето 2

Парламент уже давно вынашивал планы по созданию и законодательному закреплению "умной сортировки", ограничивающей ненужные перестановки в стране. Нашему корреспонденту удалось увидеть часть наброска к законопроекту:

Что ж. Похоже, о целесообразности подобных изысканий остается только догадываться. Ну а проверку разумности и возможности осуществления таких сортировочных действий мы оставляем читателю.

Первая строка – число `N` (количество чисел в массиве), где `N\ ≤\ 6`.

Последующие строки до конца файла – пары позиций `(i,\ j)` в массиве, элементы в которых переставляются (происходит обмен `A_i\ ↔\ A_j`).

Последовательность пар позиций `(i,\ j)`, которая вернет все на место. Каждая пара должна быть использована не больше одного раза, и те пары, которые были во входном файле, использовать нельзя. Если такой последовательности не существует, то вывести одно число 0. Если таких последовательностей несколько, то вывести любую из них.

4
1 2
3 4
2 3

1 4
1 3
2 4

2
1 2

0

6
1 6
2 5
3 4

1 2
1 3
1 4
2 3
2 4
5 6
1 5
2 6
3 5
4 5
4 6