08781. 科技节的灯光矩阵 未做

学校科技节要布展一个 $n\times n$ 的灯光矩阵：整个矩阵排成 $n$ 行 $n$ 列，共 $n^2$ 个灯位。布展要求恰好点亮 $n$ 盏彩灯，并且满足下面三个条件：

1. 每一行恰好点亮一盏灯；
2. 每一列恰好点亮一盏灯；
3. 任意两盏灯不在同一条对角线上，即任意两盏灯的行号之差的绝对值不能等于列号之差的绝对值，否则两盏灯的光会在斜向通道里互相干扰。

一个布展方案可以写成 $n$ 个数 $c_1,c_2,\dots ,c_n$，其中 $c_i$ 表示第 $i$ 行点亮的灯所在列。例如 $n=6$ 时，方案 $246135$ 表示第 $1$ 行第 $2$ 列、第 $2$ 行第 $4$ 列……各亮一盏灯。

把所有方案按字典序排列后，请输出前 $3$ 个方案，再在最后一行输出方案总数。若方案不足 $3$ 个，则把已有的全部输出；若没有合法方案，只输出一行 $0$。

一行一个正整数 $n$（$1\le n\le 13$），表示灯光矩阵的规模。

• 若存在合法方案：先每行输出一个方案，共 $n$ 个整数，整数之间用一个空格分隔，按字典序给出前 $3$ 个方案（不足 $3$ 个则全部输出）；最后一行输出一个整数，表示方案总数。
• 若不存在合法方案：只输出一行 $0$。

6

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

2

0

样例 2 解释：$2\times 2$ 的矩阵里，两盏灯无论怎么放都会同在一条对角线上，没有合法方案，只输出 $0$。

对于 $100\%$ 的数据：$1\le n\le 13$。

本题共 $10$ 个测试点，每个测试点 $10$ 分。