STABLEMP - Stable Marriage Problem

题目描述 这里有n个男人和n个女人，他们每个女人人都有自己的喜好（第一喜欢的，第二喜欢的...）男人同样也有自己对女人们的排名。你的任务是组成n对夫妻，使得他们之间不会有任意一对男女都觉得对方的配偶比自己的好（就是稳定婚姻系统...）请你写个程序来达到这个目的。 输入输出格式 输入格式： 输入t表示有t（t<=100）组数据。 第一行是n表示有n对男女。接下来的n行是女人们的喜好顺序，第i行是第i个女人的喜好顺序，接下来n行则是男人的。 输出格式： 每一组数据输出n行 每一行两个数字，m和w，m表示男人的序号，w则是女人的序号，表示这一对男女该结为夫妻 感谢@moye到碗里来 提供翻译

There are given _n_ men and _n_ women. Each woman ranks all men in order of her preference (her first choice, her second choice, and so on). Similarly, each man sorts all women according to his preference. The goal is to arrange _n_ marriages in such a way that if a man _m_ prefers some woman _w_ more than his wife, then _w_ likes her husband more than _m_. In this way, no one leaves his partner to marry somebody else. This problem always has a solution and your task is to find one.

The first line contains a positive integer _t_ <= 100 indicating the number of test cases. Each test case is an instance of the stable marriage problem defined above. The first line of each test case is a positive integer _n_ <= 500 (the number of marriages to find). The next _n_ lines are the **woman**'s preferences: _i_th line contains the number _i_ (which means that this is the list given by the _i_th woman) and the numbers of men (the first choice of _i_th woman, the second choice,...). Then, the **men**'s preferences follow in the same format.

For each test case print _n_ lines, where each line contains two numbers _m_ and _w_, which means that the **man** number _m_ and the **woman** number _w_ should get married.

2
4
1 4 3 1 2
2 2 1 3 4
3 1 3 4 2
4 4 3 1 2
1 3 2 4 1
2 2 3 1 4
3 3 1 2 4
4 3 2 4 1
7
1 3 4 2 1 6 7 5
2 6 4 2 3 5 1 7
3 6 3 5 7 2 4 1
4 1 6 3 2 4 7 5
5 1 6 5 3 4 7 2
6 1 7 3 4 5 6 2
7 5 6 2 4 3 7 1
1 4 5 3 7 2 6 1
2 5 6 4 7 3 2 1
3 1 6 5 4 3 7 2
4 3 5 6 7 2 4 1
5 1 7 6 4 3 5 2
6 6 3 7 5 2 4 1
7 1 7 4 2 6 5 3

1 3
2 2
3 1
4 4
1 4
2 5
3 1
4 3
5 7
6 6
7 2