spair

На едно състезание по танци са поканени N мъже и N women are invited. Както жените, така и мъжете са номерирани от 1 до N. Организаторите искат всичките 2*N гости да танцуват с предпочитан партньор и са поискали от всеки гост списък с предпочитания. Списъкът съдържа номерата на всички партньори от противоположния пол, подредени по намаляваща степен на предпочитание.
Преди започването на състезанието организаторите трябва да представят списък от
N двойки (мъж, жена) избрани за партньори. Казваме, че една двойка (b, f) е стабилна, когато удовлетворява следното условие: всяка жена f', която е преди f  в списъка от предпочитания на b и е в двойка с b', предпочита b' пред b. Списъкът от двойки е стабилен, ако всичките N двойки са стабилни.

Задача

По дадени числото  N и списъците с предпочитания на участниците да се намери (ако е възможно) стабилен списък от двойки.

Вход

Първият ред на файла spair.in съдържа цяло положително число N. Следващите N реда съдържат списъците с предпочитания на мъжете. Всеки списък е някаква пермутация на числата 1, 2, ..., N. Числата на ред i+1 представляват предпочитанията на мъжа с номер i по намаляваща степен на предпочитание. Следващите N реда съдържат предпочитанията на жените в абсолютно същия формат. Числата във всеки ред са разделени с интервали.

Изход

Резулаттите трябва да бъдат записани във файл spair.out на N реда. Всеки ред трябва да съдържа двойка числа от множеството {1, 2, ..., N }, представляваща елемент от намерения стабилен списък. Първото число е номер на мъж, а второто – номерът на неговата партньорка. Ако няма решение, единствения ред на файла трябва да съдържа съобщението impossible.  

Ограничения

0 < n <= 1000
Ако има повече от едно решение, във файла да се изведе само едно от тях.

Пример

spair.in

spair.out

Обяснение

3
3 1 2
2 3 1
2 3 1
2 3 1
1 3 2
1 2 3

1 3
2 1
3 2

Списъкът
1 3
2 1
3 2

е стабилен.
Да разгледаме списъка от двойки:
1 2
2 1
3 3
Този списък не е стабилен, защото двойката (1 2) не е стабилна. Наистина, мъжът с номер 1 предпочита жената с номер 3 пред своята партньорка (2), а жената с номер 3 предпочита мъжа с номер 1 пред своя партньор (3).

Ограничение за време:  0.8 секунди на тест

prof. Dana Lica
"I. L. Caragiale" National College, Ploieşti
danal182001@yahoo.com

Превод на български: Стоян Капралов