问题说明

青青草原有着举办象棋比赛的传统，今年的国际象棋组战况激烈，Gold King被杀得只剩下n个皇后。
国际象棋中的皇后可以横着移动，竖着移动，还可以斜着移动，为了让剩余的皇后可以覆盖到更多的棋盘位置，需要计算一下皇后该怎么摆放，有多少种摆法。请你帮Gold King用程序设计一下。

输入格式

输入一个整数n，表示剩余的n个皇后在n x n的棋盘中。

输出格式

输出前2种摆法和总摆法数。

样例输入1：
5
样例输入2：
8

样例输出1：
1 3 5 2 4
1 4 2 5 3
10
样例输入2：
1 5 8 6 3 7 2 4
1 6 8 3 7 4 2 5
92

提示

3<n<14
样例1输出：1 3 5 2 4表示第1个皇后放在第1行第1列，第2个皇后放在第2行第3列，第3个皇后放在第3行第5列，第4个皇后放在第4行第2列，第5个皇后放在第5行第4列。

来源/分类

算法培训-16-深度优先搜索