描述

假设一些主管每个人都可以为他们的部门招聘一名新人。这 $N$ 个部门有 $N$ 个人要被安置。每个主管都会面试所有 $N$ 个人，并根据她对自己部门中每个人的期望程度对他们进行排名（$1$ 表示“真的很想要”，$N$ 表示“真的很不想要”）。反过来，$N$ 候选人中的每一位都根据每个主管愿意为该主管工作的程度对每个主管进行排名（同样，$1$ 表示“真的想为他/她工作”，$N$ 表示“真的不想为他/她工作”）。给定每个主管对每个候选人的分数，以及每个候选人对每个经理的分数，编写一个计算机程序来确定候选人与主管的“最佳匹配”。“最佳匹配”是通过找到导致所有人总体满意度（即总和）满意度的分布来确定的。一个人离她的第一选择越近越好。如果每个人都获得他们的第一选择，则平均差异将为 $0$。

输入

输入的第一行将包含一个大于 $0$ 的整数，用于指定测试用例的数量。

下一行将包含一个整数值 $N$、$0 < N < 15$，表示主管的数量（以及员工的数量 - 有 $N$ 名主管和 $N$ 名员工）。接下来的 $N$ 行将是 $N$ 个主管中每个主管的首选项。每行将包含 $N$ 个整数条目（员工 $1$ 到 $N$ 为 $1$ 到 $N$），每个条目由一个空格字符分隔，该条目表示该主管的首选项（从最优先到最不优先）。更具体地说，该行的第一个条目将代表该主管的第一选择，第二个条目代表她的第二个选择，依此类推。接下来的 $N$ 行将是 $N$ 名员工的首选项，格式与主管相同。

输入文件中的所有数据行都将以空行结尾。

输出

对于每个测试用例，写入测试用例编号（从 $1$ 开始），后跟写入小数点右侧的 $6$ 位精度的最佳平均差。在下一行中，显示哪个最匹配（从 $1$ 开始）。在接下来的 $N$ 行中，显示每个主管（从 $1$ 开始），后跟与她匹配的员工（每行 $1$）。注意：如果有多个最佳匹配，则应按排列升序列出匹配项（请参阅示例输出）。

用空行分隔每个数据集。

输入数据 1

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

2
1 2
2 1
1 2
1 2

输出数据 1

Data Set 1, Best average difference: 0.000000
Best Pairing 1
Supervisor 1 with Employee 1
Supervisor 2 with Employee 2
Supervisor 3 with Employee 3
Supervisor 4 with Employee 4
Supervisor 5 with Employee 5
Supervisor 6 with Employee 6
Supervisor 7 with Employee 7

Data Set 2, Best average difference: 0.250000
Best Pairing 1
Supervisor 1 with Employee 1
Supervisor 2 with Employee 2