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 |
1 3 |
Списъкът
|
Ограничение
за време: 0.8 секунди
на тест
prof.
Dana Lica
"I. L. Caragiale"
danal182001@yahoo.com
Превод на
български: Стоян Капралов