求解这道DFS

在一个NN的国际棋盘上，放置N个皇后，使她们相互之间不能进攻（任意两皇后不能位置同一行、同一列、同一斜线）。 因为每行只有一个皇后，我们可以用一行N个数值来表示NN棋盘上皇后位置。 结果中第i列的数值j表示棋盘上第[i,j]位置上有一个皇后。 2 4 6 1 3 5 表示棋盘上第[1,2]、[2,4]、[3,6]、[4,1]、[5,3]、[6,5]位置上有一个皇后。

N （6≤N≤13）

前三行为先得到的三组解， 每组解为N个数，之间用空格隔开。 最后一行为总解数。

Sample Input

6

Sample Output

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