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[0] = prime[1] = false;
for(int i=2;i
Dinic 算法實現最大流#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;
}
};
struct Dinic{
int n,m,s,t;
vector edges;//存邊 邊的兩倍
vector G[maxn];//鄰接表，圖
bool vis[maxn];//BFS使用
int d[maxn];//起點到i的距離
int cur[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);
}
bool BFS(){
memset(vis,0,sizeof(vis));
queue Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while(!Q.empty()){
int x = Q.front();Q.pop();
for(int i=0;i e.flow){
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x == t || a== 0) return a;
int flow = 0,f;
for(int i= cur[x];i0){
e.flow += f;
edges[G[x][i]^1].flow -= f;
flow += f;
a -= f;
if( a== 0)break;
}
}
return flow;
}
int Maxflow(int s,int t){
this->s = s;this-> t = t;
int flow = 0;
while(BFS()){
memset(cur,0,sizeof(cur));
flow += DFS(s,INF);
}
return flow;
}
};
//EdmondsKarp Ek;
Dinic Ek;
void InitPrime(){
memset(prime,true,sizeof(prime));
prime[0] = prime[1] = false;
for(int i=2;i
