Description:


n个男生和n个女生,每个人对每个异性有一个喜欢程度排名,要求将其配成n对,使得不存在一个男生与一个女生不是一对,但均比现任伴侣更喜欢对方。

Input:


输入由多个数据组成,输入的第一行包含测试数据的数量。
每个数据之前都有一个空行。
每个数据集的输入由正整数N组成,不大于1,000,表示夫妇数量。
接下来,有N行,每行包含从1到n的所有整数,根据女孩的喜好排序。
接下来,有N行,每行包含所有从1到N的整数,根据男孩的喜好排序。

Output:


每个数据的输出由N行的序列组成,其中第i行包含数字表示男孩被分配到第i个女孩(从1到N)。
在数据之间打印空白行。

Input Sample:


Sample Output:


题解:


稳定婚姻问题的模板题,做法用Gale-Shapley算法很简单,也很好理解。
首先建立一个队列里面存放所有的为配对男生。
每一次从队列取出一个男生向他下一位喜欢的女生求婚。
如果该女生更喜欢来求婚的男生则将该女生的原配对男生放入队列,并将她与求婚男生配对。
否则将求婚男生重新放入队列。

事实证明这是对的~~~