T. 质数环

传统题

3000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Alice 正在学习数论，她想知道是否能把一个1 到 n (n为偶数) 之间所有的正整数划分成若干个不相交的环，使得每个环都至少包含三个数并且每两个相邻的数的和为质数。

即：Alice想要找到k个环 $A_1,A_2...A_k$ 满足如下情况：

1.每个环包含至少三个整数。

2.每个环的中的整数必须是 $1 \sim n$ 之间并且每个数必须出现且只能出现一次(所有的数是 $1 \sim n$ 的一个全排列)。

3.对于任意一个环 $A_i=\{a_{i,1},a_{i,2}...a_{i,l}\}$ 对于任意 $0<j<l$ $,a_{i,j}+a_{i,j+1}$ 是一个质数，且 $a_{i,l}+a_{i,1}$ 必须也是一个质数。

输入包含一个整数n(n为正整数且保证n为偶数)。

第一行输出一个整数k，表示划分成环的个数。

接下来的k行，每行第一个数l表示环中元素的个数，接下来l个数按在环中顺序依次输出，如果有多个答案，输出任意一个即可。

如果无论如何都不能满足条件,输出-1。

数据范围

$0 < n \le 10^4$

在这里给出一组输入。例如：

3
4 1 2 3 4
6 5 6 7 10 9 8
8 11 12 17 14 15 16 13 18