Rejudge Progress:
1042: 帅小伙子和俊俏姑娘
Time Limit: 2000 MS Memory Limit: 65536 KBTotal Submit: 14 Accepted: 4 Page View: 696
Submit Status Discuss
Description
南开大学冰火舞蹈团是一个云集帅小伙子和俊俏姑娘的地方。舞蹈团经常有演出任务。舞蹈团的团长需要给参加排练的同学做合适的舞伴配对,从而使整个节目能发挥出舞蹈团的较好的配合水平。
现在,有一个演出任务,需要n名帅小伙子与n名俊俏姑娘男女配对演出。当然,每个帅小伙子只能和一个俊俏姑娘配对成为舞伴。这n名帅小伙子,每个人对这n名俊俏姑娘在心里都有不同的排名,且任意两个姑娘在一个帅小伙子心目中的排名一定是不同的;同样,这n名俊俏姑娘每个人对这n名帅小伙子也都有不同的排名,且任意两个小伙子在一个俊俏姑娘心目中的排名一定是不同的。
根据舞蹈团梁团长的经验,如果一个配对组合,使得某位帅小伙子A的舞伴a在这位小伙子心目的排名不如另一位俊俏姑娘b,且这位俊俏姑娘b的舞伴B在她的心目中的排名不如这位帅小伙子A,那么帅小伙子A和俊俏姑娘b在排练的过程中就会有些情绪,演出效果可能就不大好。
现在,舞蹈团的梁团长听说你很聪明,想请你帮帮忙,在已知帅小伙子和俊俏姑娘们相互之间心目中的排名的前提下,告诉他是否存在一种合理的配对方案,使得所有的成员都能够在演出过程中不闹情绪?如果存在,请你帮他设计一组方案来为这些帅哥、靓妹们进行舞伴配对。
Input
输入包括多组测试数据,你应当处理到输入结束为止。
每组输入数据的第一行是一个正整数n,n≤50,表示有多少对舞伴。
接下来有n行,每行有n个正整数,它们介于1到n,且互不相同,其中第i行的第j列表示第i个姑娘对第j个小伙子的排名。
再接下来还有n行,每行也有n个正整数,它们也介于1到n,且互不相同,其中第i行的第j列表示第i个小伙子对第j个姑娘的排名。
Output
对于每组输入数据,输出两行。
对于第i组输入数据,输出的第一行为:”Case i:”
如果存在合适的配对方案,请输出的第二行输出一个由1到n之间互不相同的正整数组成的序列,相邻的两个正整数用一个空格隔开,第k个正整数表示第k个帅小伙子所配对的俊俏姑娘的编号,表示一种可行的配对方案;否则,请在输出的第二行输出”No Solution!”。
3
1 2 3
1 2 3
3 1 2
2 1 3
3 2 1
1 3 2
2
1 2
1 2
2 1
2 1
Case 1:
2 3 1
Case 2:
2 1