The Stable Marriage Problem

In the stable marriage problem you match the members of two equal-sized groups according to their preferences for members of the other group. You are given:

• a set $M$ of $n$ males;
• a set $F$ of $n$ females;
• for every male, a ranking of all $n$ females from most to least preferred, and for every female, a ranking of all $n$ males from most to least preferred.

A marriage is a one-to-one matching between the males and the females. A marriage is stable if there is no pair $(m, f)$ such that $f$ prefers $m$ to her current partner and $m$ prefers $f$ to his current partner. A stable marriage is male-optimal if there is no other stable marriage in which some male is matched to a female he prefers to the one assigned here.

Given the preference lists of the males and the females, find the male-optimal stable marriage.

The first line contains the number of test cases. Each test case is given as:

• a line with an integer $n$ ($0 < n < 27$);
• a line listing the $n$ male names followed by the $n$ female names, separated by spaces. Each male name is a single lowercase letter and each female name is a single uppercase letter;
• $n$ lines, each of the form x:P, where x is a male name and P is the string of all $n$ female names in his order of preference, most preferred first;
• $n$ lines, each of the form X:p, where X is a female name and p is the string of all $n$ male names in her order of preference, most preferred first.

For each test case, print the pairs of the male-optimal stable marriage, one per line as m F (a male name, a single space, then his partner's name), sorted in ascending order of the male name. Print one blank line between consecutive test cases.