409785: GYM103743 B Prime Ring Plus

Yukikaze is studying number theory. She wonders whether she can arrange all positive integers between $$$1$$$ and $$$n$$$ ($$$n$$$ is a positive even integer) into several disjoint cycles such that each cycle contains at least three integers, and the sum of any two adjacent integers is a prime number in any cycle.

Prime numbers are integers greater than $$$1$$$ and cannot be exactly divided by any positive integer other than itself and $$$1$$$.

Formally speaking, Yukikaze wants to find $$$k$$$ sequences $$$A_1, A_2, \ldots, A_k$$$ that satisfy the following conditions:

1. Each sequence contains at least three integers.
2. Each integer between $$$1$$$ and $$$n$$$ appears in exactly one sequence.
3. For any sequence $$$A_i = \{ a_{i,1}, a_{i,2}, \ldots, a_{i,l} \}$$$, $$$a_{i,j}+a_{i,j+1}$$$ is a prime number for any $$$1 \leq j < l$$$, and $$$a_{i,1}+a_{i,l}$$$ must be a prime number too.

The input contains only one positive even integer $$$n$$$ ($$$2 \leq n \leq 10^4$$$).

Output the number of cycles $$$k$$$ in the first line.

Each of the following $$$k$$$ lines starts with a positive integer $$$l$$$ denoting the number of integers in the cycle, followed by $$$l$$$ integers denoting the integers in the cycle in order. If there are multiple answers, print any. Do NOT print any extra spaces at the end of each line.

If it is impossible to arrange these $$$n$$$ integers, print $$$-1$$$ in a single line.

8

1
8 1 2 3 8 5 6 7 4

18

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