Match Maker

You run the matchmaking agency ACM (Amazing Coupling Marriage), and your job is to pair men and women into happy couples.

$N$ men and $N$ women want to get married as soon as possible. Every man ranks all $N$ women from most to least preferred, and every woman ranks all $N$ men the same way. The most preferred person is first in the list, the next is second, and so on. The table below shows one possible set of preference lists for 4 men and 4 women.

Your task is to marry every man to a woman (a one-to-one pairing) so that the result is stable. A matching is unstable if there exist a man and a woman who are not married to each other, yet each of them prefers the other over their current partner. Such a pair would rather leave their partners for each other, so the marriage is fragile. A matching with no such pair is stable.

For example, the matching where man 1 marries woman 3, man 2 marries woman 1, man 3 marries woman 4, and man 4 marries woman 2 is unstable, because man 1 prefers woman 1 over woman 3 and woman 1 prefers man 1 over man 2.

For a given set of preference lists there are usually several stable matchings. Among them, output the man-optimal one: the unique stable matching in which every man gets the best partner (highest on his own preference list) that he could have in any stable matching. This is exactly the matching produced by the men-proposing Gale-Shapley procedure, where free men propose down their lists and each woman keeps her most preferred proposer so far.

The first line contains the number of test cases $T$.

Each test case begins with a line containing an integer $N$ with $1 \le N < 100$: there are $N$ men and $N$ women, all numbered from $1$ to $N$.

The next $N$ lines give the men's preferences. Line $i$ contains a permutation of $1..N$: the preference list of man $i$ over the women, from most to least preferred (he prefers woman $X$ to woman $Y$ if $X$ comes before $Y$).

The following $N$ lines give the women's preferences in the same format: line $j$ is the preference list of woman $j$ over the men.

For each test case, print exactly one line describing the man-optimal stable matching.

The line lists the partners' woman ids ordered by increasing man id: the first number is the woman married to man $1$, the second number is the woman married to man $2$, and in general the $i$-th number is the woman married to man $i$. Separate the numbers with single spaces.