Стабільний шлюб
Задача стабільного одруження полягає у встановленні пар між членами двох множин на основі їхніх уподобань. Вхідні дані включають:
множину M з n чоловіків;
множину F з n жінок;
для кожного чоловіка і кожної жінки є список членів протилежної статі, впорядкований за уподобаннями (від найбільш бажаного до найменш бажаного).
Одруженням називається однозначне відображення між чоловіками та жінками. Одруження є стабільним, якщо не існує такої пари (m, f), що f ∈ F надає перевагу m ∈ M своєму поточному партнеру, а m надає перевагу f своєму поточному партнеру. Стабільне одруження A називається оптимальним відносно чоловіків, якщо не існує такого стабільного одруження B, в якому будь-який чоловік отримує жінку, яку він більше надає перевагу, ніж ту, яка призначена йому в A.
На основі заданих списків уподобань для кожного чоловіка і кожної жінки необхідно знайти стабільне одруження, оптимальне відносно чоловіків.
Вхідні дані
Перша стрічка містить кількість тестів. Перша стрічка кожного тесту містить ціле число n (0 < n < 27). У наступному рядку наведені імена n чоловіків і n жінок. Імена чоловіків починаються з великої літери, а жіночі — з великої. Далі йдуть n рядків, що описують списки уподобань для чоловіків. Наступні n рядків описують списки уподобань для жінок.
Вихідні дані
Для кожного тесту слід вивести пари стабільного одруження, оптимального відносно чоловіків. Пари слід виводити в лексикографічному порядку чоловічих імен, як показано в прикладі. Між тестами слід виводити порожній рядок.