7857: BZOJ3857：Multiplication table

Teacher Mai has a multiplication table in base p. For example, the following is a multiplication table in base 4: * 0 1 2 3 0 00 00 00 00 1 00 01 02 03 2 00 02 10 12 3 00 03 12 21 But a naughty kid maps numbers 0..p-1 into another permutation and shuffle the multiplication table. For example Teacher Mai only can see: 1*1=11 1*3=11 1*2=11 1*0=11 3*1=11 3*3=13 3*2=12 3*0=10 2*1=11 2*3=12 2*2=31 2*0=32 0*1=11 0*3=10 0*2=32 0*0=23 Teacher Mai wants you to recover the multiplication table. Output the permutation number 0..p-1 mapped into. It's guaranteed the solution is unique.

输入格式

There are multiple test cases, terminated by a line "0". For each test case, the first line contains one integer p(2<=p<=500). In following p lines, each line contains 2*p integers.The (2*j+1)-th number x and (2*j+2)-th number y in the i-th line indicates equation i*j=xy in the shuffled multiplication table. Warning: Large IO!

输出格式

For each case, output one line. First output "Case #k:", where k is the case number counting from 1. The following are p integers, indicating the permutation number 0..p-1 mapped into.

样例输入

4
2 3 1 1 3 2 1 0
1 1 1 1 1 1 1 1
3 2 1 1 3 1 1 2
1 0 1 1 1 2 1 3
0

样例输出

Case #1: 1 3 2 0

提示

没有写明提示

题目来源

By 镇海中学 鸣谢David Lee重新制作数据