|
B |
Match Maker Input: Standard Input Output: Standard Output |
|
|
There are N men and N women in a certain institution. Each of the N men provides you with a list that contains the names of the women who they would prefer to marry.
You would like to apply your programming knowledge into this match making to make all the men satisfied.
A man is satisfied if he is assigned with a woman whom he has in his preference list. You must ensure that each man is assigned to exactly one woman and vice versa.
|
|
Input
The first line of input is an integer T(T < 50) that indicates the total number of test cases. Each case starts with a line containing a positive integer N(N < 16). The next line gives the names of the N men. Consecutive names are separated by a single space character and each name can be up to 20 lowercase characters. The next line gives the names of the N women in the same format. The next N lines give you the list of the women that each man prefers. Each of these N lines starts with the name of a man followed by a colon followed by a list of the women in his corresponding list. All the name of women are preceded by a single space.
You may assume that all the names of the N men and N women are distinct. However a man and a woman can have the same name. The list of women in each man’s list will be from the given set of women and there won’t be any duplicates.
Output
For each case, output the case number first. In the next line output the total number of distinct assignments that are valid. Two assignments are different if there is a matching between one man and one woman that is not common to both. In the next line, output the assignment that is lexicographically the smallest. You should print the names of each pair one after another with the man’s name preceding that of his matched woman. The sample clarifies what lexicographically smallest means.
If the case is such that it’s not possible to satisfy all the men, then output “No Way” instead.
Note that there are no trailing/leading spaces in the input and output.
Look at the samples for clarifications and detailed analysis.
Sample Input Output for Sample Input
|
3 3 bill
john seher sabah marsha john: sabah bill: marsha 2 lou liu zai kai lou: kai zai liu: 3 andy simon bob donna steph mary simon: donna steph mary bob: donna mary steph andy: steph mary donna |
Case 1: 1 Case 2: Case 3: 6 andy donna bob mary simon steph |
Problem
setter: Sohel Hafiz, Special Thanks: Shamim Hafiz,
Illustration
Case 1:
Each man likes exactly one woman and each woman is liked by exactly one man. So there is only one assignment possible.
Case 2:
liu doesn’t like anyone and so it’s impossible to satisfy all the men.
Case 3:
All the 3 men like every women and so any permutation is a valid assignment. Of all the 6 assignments “andy donna bob mary simon steph” is the lexicographically smallest string. Note that “andy donna bob mary simon steph” and
“bob mary andy donna simon steph” are same assignment. The former gets printed since it’s lexicographically smaller.