eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Стабильное бракосочетание

Стабильное бракосочетание

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Задача стабильного бракосочетания состоит в установлении отношений между членами двух множеств в соответствии с их предпочтениями. Входные данные состоят из:

  • множества M из n мужчин;

  • множества F из n женщин;

  • для каждого мужчины и каждой женщины имеется список членов противоположного пола, заданный в порядке предпочтения (от наиболее предпочтительного до наименее).

Бракосочетанием будем называть однозначное отображение между мужчинами и женщинами. Бракосочетание будем называть стабильным, если не существует такой пары (m, f) что fF предпочитает mM своему текущему партнеру, а m предпочитает f своему текущему партнеру. Стабильное бракосочетание A называется оптимальным по отношению к мужчинам, если не существует такого стабильного бракосочетания B, в котором какому-нибудь мужчине соответствует женщина, которую он больше предпочитает, нежели та, которая присвоена ему в A.

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

Входные данные

Первая строка содержит количество тестов. Первая строка каждого теста содержит целое число n (0 < n < 27). В следующей строке заданы имена n мужчин и n женщин. Мужские имена начинаются прописными буквами, а женские заглавными. Далее идут n строк, которые описывают списки предпочтений для мужчин. Следующие n строк описывают списки предпочтений для женщин.

Выходные данные

Для каждого теста следует вывести пары стабильного бракосочетания, оптимального по отношению к мужчинам. Пары следует выводить в лексикографическом порядке мужских имен как показано в примере. Между тестами следует выводить пустую строку.

Пример

Входные данные #1
2
3
a b c A B C
a:BAC
b:BAC
c:ACB
A:acb
B:bac
C:cab
3
a b c A B C
a:ABC
b:ABC
c:BCA
A:bac
B:acb
C:abc
Выходные данные #1
a A
b B
c C

a B
b A
c C