如果要相邻两个数（a[i] >= 2）相加为质数，显然它们的奇偶性不同，也就是说一个圆桌（环）必须是偶环。
也就是答案的若干个环组成了一张二分图，其中以奇偶分色。
考虑每个点的度数一定为2，用最大流解决：
- 让源点向所有的奇数点连流量为2的边。
- 让所有的偶数点向汇点连流量为2的边。
- 当且仅当一组奇数和偶数相加为质数时，连一条流量为1的边。
可以证明，如果最大流小于n，那就不存在解，否则一定存在若干个边数大于2的偶环，使得所有点只出现在一个环里，最后Dfs找出环即可。
$ \bigodot $ 技巧&套路：
- 根据奇偶性或网格图黑白染色，想到建立二分图。
- 最大流的模型。
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm> const int N = , M = ; int n, s, t, tot, a[N], vis[N], lc[N], rc[N], ln, rn;
int ntp[];
std::vector<int> an[N]; void Init() {
ntp[] = ;
for (int i = ; i <= ; ++i) if (!ntp[i]) {
for (int j = i * i; j <= ; j += i) {
ntp[j] = ;
}
}
} namespace GR {
int yun = , cur[N], las[N], to[M << ], pre[M << ], fl[M << ];
int h[N], gap[N];
inline void Add(int a, int b, int c) {
to[++yun] = b; fl[yun] = c; pre[yun] = las[a]; las[a] = yun;
to[++yun] = a; fl[yun] = ; pre[yun] = las[b]; las[b] = yun;
}
int Isap(int x, int flo, int usd = ) {
if (x == t) return flo;
for (int i = cur[x]; i; i = pre[i]) if (fl[i] > && h[to[i]] + == h[x]) {
int f = Isap(to[i], std::min(flo, fl[i]));
usd += f; fl[i] -= f; fl[i ^ ] += f;
if (fl[i] > ) cur[x] = i;
if (usd == flo) return flo;
}
if (gap[h[x]] == ) h[s] = t + ;
--gap[h[x]]; ++gap[++h[x]];
cur[x] = las[x];
return usd;
}
int Max_flow(int re = ) {
memset(h, , sizeof h);
memset(gap, , sizeof gap);
for (; h[s] < t + ; ) re += Isap(s, 1e9);
return re;
}
} void Build() {
s = n + ; t = n + ;
for (int i = ; i <= n; ++i) {
if (a[i] & ) {
lc[++ln] = i; GR::Add(s, i, );
} else {
rc[++rn] = i; GR::Add(i, t, );
}
}
for (int i = ; i <= ln; ++i) {
for (int j = ; j <= rn; ++j) {
if (!ntp[a[lc[i]] + a[rc[j]]]) {
GR::Add(lc[i], rc[j], );
}
}
}
} void Dfs(int gr, int x) {
an[gr].push_back(x);
vis[x] = ;
for (int i = GR::las[x]; i; i = GR::pre[i]) {
int v = GR::to[i];
if (vis[v] || v == s || v == t) continue;
if (((~i & ) && GR::fl[i] == ) || ((i & ) && GR::fl[i] == )) {
Dfs(gr, v);
}
}
} int main() {
Init();
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
}
Build(); int ans = GR::Max_flow();
if (ans != n) {
puts("Impossible"); return ;
}
for (int i = ; i <= n; ++i) {
if (!vis[i]) Dfs(++tot, i);
}
printf("%d\n", tot);
for (int i = ; i <= tot; ++i) {
printf("%d ", (int)an[i].size());
for (int j = ; j < (int)an[i].size(); ++j) {
printf("%d ", an[i][j]);
}
putchar('\n');
} return ;
}