题目描述

稳定婚姻问题需要将两个不同集合的成员根据他们对另一集合成员的偏好进行匹配。问题的输入包括：

• 一个包含n个男性的集合M；
• 一个包含n个女性的集合F；
• 对于每个男性和女性，都有一个按偏好顺序排列的另一性别成员的列表（从最喜欢到最不喜欢）。

婚姻是一种男性与女性之间的一一映射。如果不存在一对(m, f)使得f ∈ F更喜欢m ∈ M而不是她当前的伴侣，同时m更喜欢f而不是他当前的伴侣，则称该婚姻是稳定的。如果不存在其他稳定婚姻B，使得任何男性在B中匹配的女性比在A中更受其喜欢，则称稳定婚姻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

来源

Southeastern Europe 2007