题目描述

给定正偶数 \(n\)，把 \(1\sim n\) 排成一个环，要求相邻两个数的和均是质数，编程求出符合这个条件的环的方案数，注意所有数的相对关系保持不变的属于同一种方案。例如：当 \(n＝4\) 时，\(1,2,3,4\) 和 \(1,4,2,3\) 是两种不同的方案，而 \(1,2,3,4\) 和\(2,3,4,1\) 属于同一种方案。并按字典序输出前 \(k\) 种方案。

格式

输入格式

正偶数 \(n(≤18)\) 和正整数 \(k(≤10000)\)。

输出格式

第 \(1\) 行到第 \(k\) 行输出符合条件的排列，如果总方案数不足 \(k\) 个，则全部输出； 最后一行输出方案数。

样例1

输入样例1

4 2

输出样例1

1 2 3 4
1 4 3 2
2

限制

第 \(1\) 至 \(7\) 个数据，\(n≤16\)；

第 \(8 \sim 10\) 个数据，\(n=18\)。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T3\)

文件IO

freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);