## 1119 - The Stable Marriage Problem

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 11

Solved: 5

Description
The stable marriage problem consists of matching members of two different sets according
to the member’s preferences for the other set’s members. The input for our problem consists of:
• a set M of n males;
• a set F of n females;
• for each male and female we have a list of all the members of the opposite gender
in order of preference (from the most preferable to the least).
A marriage is a one-to-one mapping between males and females. A marriage is called
stable, if there is no pair (m, f) such that f ∈ F prefers m ∈ M to her current partner and m prefers
f over his current partner. The stable marriage A is called male-optimal if there is no other stable
marriage B, where any male matches a female he prefers more than the one assigned in A.
Given preferable lists of males and females, you must find the male-optimal stable
marriage.
Input
The first line gives you the number of tests. The first line of each test case contains integer
n (0 < n < 27). Next line describes n male and n female names. Male name is a lowercase letter,
female name is an upper-case letter. Then go n lines, that describe preferable lists for males.
Next n lines describe preferable lists for females.
Output
For each test case find and print the pairs of the stable marriage, which is male-optimal.
The pairs in each test case must be printed in lexicographical order of their male names as
shown in sample output. Output an empty line between test cases.
sample input
```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 ```
sample output
```a A
b B
c C

a B
b A
c C ```
hint
source
Southeastern European Regional Programming Contest Bucharest, Romania October 27, 2007
© 2015 HUST ACMICPC TEAM. All Right Reserved.