<<Previous

Next>>

　　 南开大学冰火舞蹈团是一个云集帅小伙子和俊俏姑娘的地方。舞蹈团经常有演出任务。舞蹈团的团长需要给参加排练的同学做合适的舞伴配对，从而使整个节目能发挥出舞蹈团的较好的配合水平。
　　现在，有一个演出任务，需要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!”。

Sample Input

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

Sample Output

Case 1:
2 3 1
Case 2:
2 1

Source

第三届南开大学程序设计网上竞赛“我为程序狂”(NKPC3)

Best User : wysuperfly

If the buttons do not work well , you may try Submit , Status , Post , 0 post(s), Back .

Editor : wysuperfly | Last update : wysuperfly | History

Update history:wysuperfly,wysuperfly,wysuperfly