Задача №111141. Обмен
Двум одинаковым группам школьников по N человек каждая предполагалось выдать по одинаковому комплекту из N книг. Однако школьники не дослушали кому какие книги брать и каждый взял первую попавшуюся книгу.
Чтобы спасти ситуацию, школьники были построены в два ряда один напротив другого, и каждый держал в руках свою книгу. Книга подлежит обмену тогда и только тогда, когда обе ее копии оказались в одном ряду.
Вы должны сказать какие школьники должны поменяться с какими (очевидно из противоположного ряда), чтобы в каждом ряду оказался комплект из различных книг, а общее число обменов было минимальным или определите, что обмены не нужны. При этом должны выполняться следующие условия на один обмен:
- Обе обмениваемые книги нуждаются в обмене.
- Участники обмена или стоят друг напротив друга или на одного человека левее или правее.
- Каждый человек должен участвовать в обмене не более одного раза.
Первая строка входных данных содержит число N, обозначающее число детей (1 ≤ N ≤ 1 000). В каждой из следующих N строк находятся два целых числа ai и bi (1 ≤ ai, bi ≤ N). ai обозначает название книги в руках i-го ребенка в первом ряду, bi обозначает название книги в руках i-го ребенка во втором ряду соответственно. Названия книг пронумерованы с 1.
Выведите одно число -1, если описанные обмены ведущие к нужному перераспределению книг произвести невозможно. В противном случае первая строка должна содержать число обменов K. Следующие K строк описывают последовательность обменов. Каждая такая строка должна содержать пару чисел Xi, Yi, где Xi — номер ребенка в первом ряду, Yi — номер ребенка во втором ряду. Нумерация детей также ведется с 1. Если существует несколько планов обмена, то выведите любой.
4
1 2
1 2
4 3
4 3
2
1 2
4 4
6
1 2
2 3
3 4
5 4
6 5
1 6
-1
Подзадача 1. N не превосходит 20. Решение оценивается в 40 баллов
Подзадача 2. Дополнительные ограничения отсутствуют. Решение оценивается в 60 баллов