1524: 聪明格

聪明格是一种数字游戏，又堪称升级版的数独，诞生日本。它在数学上的要求比数独要高得 多，它把数独规则与加减乘除四则运算相结合，使大脑在各种谜题中来回穿梭。

----摘自百度百科

它的规则是这样的：

有一个n*n的棋盘，每个格子里填一个在1~n范围内的数，使得每行每列没有重复的数字， (即1~n每个数在每行和每列各出现一次)，且满足下列条件：

现在给你一个n*n的棋盘，让你完成它，并输出解的个数和字典序最小的方案。

数据保证一定有解。

第一行一个正整数n，表示棋盘的行数和列数。

接下来n行，每行n个正整数。表示：相同数字构成了许多个连通块，假设这个四连通块内 每个数字都为a,那么你在这些格子上填的数的乘积应该等于a。（具体描述见样例）

输出共n+1行，第一行输出解的个数

接下来n行，每行n个正整数。表示n*n的矩阵里每个数字的值（字典序最小的方案）。

输入样例 1
4 6
6 1 144
6 2 144 144
4 2 144 4
12 12 4 4
注： 此样例所对应 4*4 的棋盘即为上图。

输入样例 2
3 1
2 12 18
12 12 18
18 18 18

输入样例 3
9 3
2 35 35 42 42 54 54 54 4
32 27 35 576 10 108 108 108 4
9 27 576 576 10 40 40 1008 1008
9 270 576 576 8 14 14 1008 1008
14 270 270 576 8 105 32 8 3
14 4 2688 27 27 105 32 8 10
30 2688 2688 80 6 105 63 63 10
30 2688 126 80 80 24 3 63 9
6 6 126 126 126 24 24 40 40

输出样例 1
1 2
3 1 4
1 2 4 3
4 1 3 2
3 4 2 1

输出样例 2
4 1
2 3
2 3 1
3 1 2

输出样例 3
1 8
1 5 6 7 9 2 3 4
4 3 7 8 5 6 9 2 1
1 9 4 3 2 8 5 6 7
9 5 3 1 8 2 7 4 6
7 6 9 2 1 5 4 8 3
2 4 6 9 3 7 8 1 5
5 7 8 4 6 3 1 9 2
6 8 2 5 4 1 3 7 9
3 2 1 7 9 4 6 5 8