#OJ2285. 魔法矩阵

魔法矩阵

魔法矩阵

Time Limit: 2 Sec  Memory Limit: 128 MB

Description

给你一个n*n的矩阵,从中选择n个数,任意两个数不在同一列或者同一行,并使得这n个数中的最大值与最小值之差的绝对值最小。输出这个最小的绝对值以及相应的解。

Input

第一行为一个正整数T,代表样例组数。 每组样例的第一行为一个正整数n(n<=16),代表矩阵的长和宽。 接下来n行,每行有n个元素,代表矩阵对应位置上的元素,每个元素的取值范围为[1,1000]。

Output

对于每组样例,输出的第一行为所求的最小绝对值,第二行为n个数,分别代表第1-n行所选择的数在哪一列。

Sample Input

2
2
1 2
3 4
2
1 1
1 1

Sample Output

1
2 1
0
1 2

HINT

直接搜的话肯定会tle的,尝试使用剪枝来优化。