All submissions for this problem are available.
The prom night is here and it's time for the youngsters to chose their partners and ask them out. But the scene in your college seems pathetic. No one has chosen their partners yet and are reluctant to go ahead and ask someone.
You decide to take up the task in your hands and make happy matches between boys and girls, by making them fill a preference form.
Each boy and each girl has a list of preferences for all the people of the opposite sex. The most preferable person will come at the first position in the list, the second preferable person will come at the next and so on. The table below shows a set of preference lists that might exist among 4 boys and 4 girls.
1B : 2G 4G 1G 3G
2B : 1G 2G 3G 4G
3B : 2G 3G 2G 4G
4B : 1G 3G 2G 4G
1G : 4B 1B 2B 3B
2G : 4B 3B 2B 1B
3G : 1B 4B 2B 3B
4G : 3B 2B 1B 4B
Your task is to make matches of all the boys to all the girls in such a way as to respect all their preferences as much as possible. However, you must assume that anyone assigned to someone other than their first choice will be disappointed and will always prefer anyone higher up on the list. If the N matches are chosen such that there exist a boy and a girl who are not coupled with each other, but who would both prefer each other to their actual dance partners, then the matches are said to be unstable. If no such pairs exists, it is called stable.
A match (1B 3G) (2B 1G) (3B 4G) (4B 2G) is unstable because 1B prefers 1G to 3G, and 1G prefers 1B to 2B.
The unstable couples might get into an altercation spoiling the prom night; this is a definitely bad situation that you want to avoid.
In general, there are many diffferent stable matches for a given set of preference lists. Your task is to print just one stable match among them.
The input consists of T test cases. The number of test cases (T) is given in the first line of the input file.
Each test case begins with a line containing an integer N less than 100, indicating that N boys and N girls are given. The following N lines represent nthe boys' preferencences for the girls, where the ith line contains the preference list of a boy with id i in order of preferences of the N girls; he prefers a girl X to another girl Y if X precedes Y in the list. The following N lines represent the girls' preferences for the N boys. Assume that all boys and all girls have consecutive id-numbers from from 1 to N.
Print exactly one line for each test case. The line should contain a stable match for the test case. Each match should be represented as a sequence of the girls' id, according to the increasing order of boys' id. The girl with the first id in the match is a partner of the boy with id '1' , the girl with the second id in the match is a partner of the boy with id 'i' . The consecutive girls' id in the match should be separated by a single space.
Input: 2 3 1 2 3 3 2 1 2 1 3 1 2 3 3 2 1 2 1 3 4 2 4 1 3 1 2 3 4 2 3 4 1 2 3 1 4 4 1 2 3 4 3 2 1 1 4 2 3 3 2 1 4 Output: 1 3 2 1 3 4 2
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, D, PERL, FORT, ADA, ASM, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, TCL, PERL6, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.