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 test(s) input
4
3 4 8 9
output
1
4 1 2 4 3
input
5
2 2 2 2 2
output
Impossible
input
12
2 3 4 5 6 7 8 9 10 11 12 13
output
1
12 1 2 3 6 5 12 9 8 7 10 11 4
input
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
output
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
Note In example 1, they can sit around one table, their ages are: 3-8-9-4, adjacent sums are: 11, 17, 13 and 7, all those integers are primes.
In example 2, it is not possible: the sum of 2+2 = 4 is not a prime number.
题意是给n个数，分成几桌，要求一桌上的数字相邻数字之和是质数，数字首尾相连。
由题意可知，每个数字大于等于2，则和为质数说明两个数一个是奇数一个是偶数，则奇数偶数的个数相等，则把奇数 偶数分成两堆，建一个二分图，起点连接所有的奇数，权值为2，终点连接所有的偶数，权值为2，奇数与偶数之和为质数，则连一条1的边，求最大流，如果最终的结果，从起点出发有权值为1的边，则说明最多只有两个人能连起来，不合题意，无解，每个奇点 偶点都有两个边相连，用dfs找出这个路径，如果大于3个连接点，则输出答案即可！这里用EK算法bfs实现求最大流！
?
#define INF 9000000000
#define EPS (double)1e-9
#define mod 1000000007
#define PI 3.14159265358979
//*******************************************************************************/
#endif
#define N 205
#define M 100005
#define maxn 205
#define MOD 1000000000000000007
int n,pri[N],ansNum;
bool vis[N],prime[M];
vector
ans[N];
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
struct EdmondsKarp{
int n,m;
vector
edges;//存边 边的两倍 vector
G[maxn];//邻接表，图 int a[maxn];//起点到i的可改进量 int p[maxn];//最短路入弧号 void init(int n){ FI(n) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap){ edges.push_back(Edge(from,to,cap,0)); edges.push_back(Edge(to,from,0,0));//反向 m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } int Maxflow(int s,int t){ int flow = 0; for(;;){ memset(a,0,sizeof(a)); queue
Q; Q.push(s); a[s] = INF; while(!Q.empty()){ int x = Q.front();Q.pop(); FI(G[x].size()){ Edge & e = edges[G[x][i]]; if(!a[e.to]&&e.cap > e.flow){ p[e.to] = G[x][i]; a[e.to] = min(a[x],e.cap - e.flow); Q.push(e.to); } } if(a[t]) break; } if(!a[t]) break; for(int u = t;u !=s;u = edges[p[u]].from){ edges[p[u]].flow += a[t]; edges[p[u] ^ 1].flow -= a[t]; } flow += a[t]; } return flow; } }; EdmondsKarp Ek; void InitPrime(){ memset(prime,true,sizeof(prime)); prime[