Fox Ciel is participating in a party in Prime Kingdom. There are n foxes there (include Fox Ciel). The i-th fox is ai years old.
They will have dinner around some round tables. You want to distribute foxes such that:
- Each fox is sitting at some table.
- Each table has at least 3 foxes sitting around it.
- The sum of ages of any two adjacent foxes around each table should be a prime number.
If k foxes f1, f2, ..., fk are sitting around table in clockwise order, then for 1 ≤ i ≤ k - 1: fi and fi + 1 are adjacent, and f1 and fk are also adjacent.
If it is possible to distribute the foxes in the desired manner, find out a way to do that.
Input
The first line contains single integer n (3 ≤ n ≤ 200): the number of foxes in this party.
The second line contains n integers ai (2 ≤ ai ≤ 104).
Output
If it is impossible to do this, output "Impossible".
Otherwise, in the first line output an integer m (): the number of tables.
Then output m lines, each line should start with an integer k -=– the number of foxes around that table, and then k numbers — indices of fox sitting around that table in clockwise order.
If there are several possible arrangements, output any of them.
Sample Input
4
3 4 8 9
1
4 1 2 4 3
5
2 2 2 2 2
Impossible
12
2 3 4 5 6 7 8 9 10 11 12 13
1
12 1 2 3 6 5 12 9 8 7 10 11 4
24
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3
6 1 2 3 6 5 4
10 7 8 9 12 15 14 13 16 11 10
8 17 18 23 22 19 20 21 24
建二分图，再用流量为2限制度数，即可用网络流AC。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int N=,M=,INF=;
int cnt,fir[N],fron[N],nxt[M],to[M],cap[M];
int dis[N],gap[N],path[N],vis[N],q[N],h,t;
int n,m,a[N],tp[N],tot;vector<int>ans[N];
struct Net_Flow{
void Init(){
memset(fir,,sizeof(fir));
memset(gap,,sizeof(gap));
memset(dis,,sizeof(dis));
h=t=cnt=;
}
void addedge(int a,int b,int c){
nxt[++cnt]=fir[a];to[fir[a]=cnt]=b;cap[cnt]=c;
nxt[++cnt]=fir[b];to[fir[b]=cnt]=a;cap[cnt]=;
}
bool BFS(int S,int T){
dis[q[h]=T]=;
while(h<=t){
int x=q[h++];
for(int i=fir[x];i;i=nxt[i])
if(!dis[to[i]])dis[q[++t]=to[i]]=dis[x]+;
}
return dis[S];
}
int ISAP(int S,int T){
if(!BFS(S,T))return ;
for(int i=S;i<=T;i++)gap[dis[i]]+=;
for(int i=S;i<=T;i++)fron[i]=fir[i];
int ret=,f,p=S,Min;
while(dis[S]<=T+){
if(p==T){f=INF;
while(p!=S){
f=min(f,cap[path[p]]);
p=to[path[p]^];
}ret+=f,p=T;
while(p!=S){
cap[path[p]]-=f;
cap[path[p]^]+=f;
p=to[path[p]^];
}
}
for(int &i=fron[p];i;i=nxt[i])
if(cap[i]&&dis[to[i]]==dis[p]-){
path[p=to[i]]=i;break;
}
if(!fron[p]){
if(!--gap[dis[p]])break;Min=T+;
for(int i=fir[p];i;i=nxt[i])
if(cap[i])Min=min(Min,dis[to[i]]);
gap[dis[p]=Min+]+=;fron[p]=fir[p];
if(p!=S)p=to[path[p]^];
}
}
return ret;
}
void DFS(int x,int id){
vis[x]=;ans[id].push_back(x);
for(int i=fir[x];i;i=nxt[i]){
if(vis[to[i]]||to[i]<||to[i]>n)continue;
if(a[to[i]]%==&&cap[i^]==)DFS(to[i],id);
if(a[to[i]]%!=&&cap[i]==)DFS(to[i],id);
}
}
void Solve(int S,int T){
for(int x=;x<=n;x++)
if(a[x]%==&&!vis[x])
DFS(x,++tot);
printf("%d\n",tot);
for(int i=;i<=tot;i++){
printf("%d ",ans[i].size());
for(int j=;j<ans[i].size();j++)
printf("%d ",ans[i][j]);
puts("");
}
}
}isap;
int S,T;
bool Check(int x){
for(int i=;i*i<=x;i++)
if(x%i==)return false;
return true;
}
int main(){
scanf("%d",&n);isap.Init();T=n+;
if(n%==){puts("Impossible");return ;}
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=;i<=n;i++){
if(a[i]%==)isap.addedge(S,i,);
else isap.addedge(i,T,);
}
for(int i=;i<=n;i++)if(a[i]%==)
for(int j=;j<=n;j++)if(a[j]%)
if(Check(a[i]+a[j]))
isap.addedge(i,j,);
if(isap.ISAP(S,T)!=n){
puts("Impossible");
return ;
}
isap.Solve(S,T);
return ;
}