题目描述

题目译自 Ukrainian Olympiads in Informatics 2025 Stage 4 Day2 T4. Проста задача

我们称一个非空的正整数序列为奇怪的，如果其元素之和是一个质数。

给定一个长度为 $n$ 的数组 $a$，数组元素均为质数。同时给定一个整数 $k$。

你需要将数组 $a$ 分成 $k$ 个非空的子序列，使得数组 $a$ 的每个元素恰好属于一个子序列，并且在所形成的子序列中，奇怪的子序列数量尽可能少。

在本题中，每个测试包含多个输入数据组。你需要为每个数据组独立解决问题。

注意：本题中没有「无附加限制」的子任务。

序列 $c$ 称为数组 $b$ 的子序列，如果可以通过从数组 $b$ 中删除若干元素（可能是零个），使得剩余元素组成序列 $c$。

输入格式

输入的第一行包含一个整数 $T$ $(1 \le T \le 10^5)$，表示输入数据组的数量。接下来是各数据组的描述。

每个数据组的第一行包含两个整数 $n$ 和 $k$ $(1 \le k \le n \le 10^5)$，分别表示数组 $a$ 的长度和需要划分的子序列数量。

每个数据组的第二行包含 $n$ 个质数 $a_1, a_2, \ldots, a_n$ $(2 \le a_i \le 10^5, a_i \le a_{i+1})$，表示数组 $a$ 的元素。

保证所有数据组中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个数据组，输出最优划分，格式如下：

• 第一行输出一个整数 $m$，表示所形成的子序列中奇怪的子序列数量；
• 接下来的 $k$ 行，每行输出整数 $s_i$ 以及 $b_1, b_2, \ldots, b_{s_i}$ $(1 \le s_i \le n)$，分别表示对应子序列中的元素数量及其元素。

子序列及其元素的输出顺序可以任意。

如果存在多个正确答案，可以输出任意一个。

4
3 1
5 5 13
4 2
2 3 5 7
5 3
3 3 5 5 13
6 5
2 2 2 3 3 3

1
3 13 5 5
0
2 2 7
2 3 5
1
1 13
2 3 3
2 5 5
4
1 2
1 2
1 2
1 3
2 3 3

数据范围与提示

详细子任务附加限制及分值如下表所示：