1034: 能量项链
Memory Limit:128 MB
Time Limit:4.000 S
Judge Style:Text Compare
Creator:
Submit:167
Solved:35
Description
质数总是蕴含着无穷的能量。Lancer在使用了辅助配件改装的武器之后,轻松地取得了战斗的胜利。
他对于项链有着谜一般的执着,在感受到了质数特征值配件改装后的武器所产生的巨大能量之后,他决定请工匠为他打造一款由质数特征值组成的能量项链。
现在已知Lancer有N个魔法石,其能量值分别为1、2、3、…、N。众所周知,项链是一个环形(头尾相连)物品,Lancer想要用这N块魔法石打造一款项链,满足:对于项链上任意一块魔法石,它的能量值与它相邻的两块魔法石之和为一个质数。
现在Lancer想要知道如何设计魔法石在项链上的摆放次序,才能够满足他苛刻的条件呢?
(提示:由于项链是环形,因此我们规定输出的方案第一个数字必须是1,而且必须按照按照字典序从小到大输出,避免DFS全排列导致的输出方案重复。)
例如,当N=6时,下图是一个可行的方案:
即1 4 3 2 5 6
Input
输入文件名为 necklace.in。
输入共1行:第一行为1个正整数N,代表Lancer有N个魔法石
Output
输出文件名为 necklace.out。
输出有若干行,每一行有N个正整数,以空格分隔,表示方案
若无解,则输出"No"。
Sample Input Copy
4
Sample Output Copy
1 2 3 4
1 4 3 2
HINT
注意,若N=3,则你应该输出No.
【数据范围】
对于100%的数据 2 ≤ N ≤ 18