#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#define ll long long
#include <bits/stdc++.h>
using namespace std;
static vector<ll> adj[1012];
void Alice( int N, int M, int A[], int B[] ){
if (N==1){
InitG(1,0);
return;
}
ll cnt=0;
for (int i=0;i<M;i++){
adj[A[i]].emplace_back(B[i]);
cnt++;
}
for (int i=0;i<N;i++){
for (int j=0;j<10;j++){
if (i & (1<<j)){
adj[N+j].emplace_back(i);
cnt++;
}
}
}
cnt+=N+10+10+9;
InitG(N+12,cnt);
for (int i=0;i<N+10;i++){
--cnt;
MakeG(cnt,i,N+10);
}
for (int i=N;i<N+10;i++){
--cnt;
MakeG(cnt,i,N+11);
}
for (int i=N;i<N+9;i++){
--cnt;
MakeG(cnt,i,i+1);
}
for (int i=0;i<1012;i++){
for (auto u:adj[i]){
--cnt;
MakeG(cnt,i,u);
}
}
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#define ll long long
#include <bits/stdc++.h>
using namespace std;
vector<ll> bits;
static ll adj[1012][1012];
ll deg[1012];
ll bitsDeg[1012];
ll vis[1012];
ll idx[1012];
map<ll,ll> m;
vector<ll> out[1012];
void Bob( int V, int U, int C[], int D[] ){
if (V==1){
InitMap(1,0);
return;
}
for (int i=0;i<U;i++){
adj[C[i]][D[i]]=true;
adj[D[i]][C[i]]=true;
deg[C[i]]++,deg[D[i]]++;
}
ll md=0;
for (int i=1;i<V;i++){
if (deg[i]>deg[md]) md=i;
}
ll hub=0;
for (int i=0;i<V;i++){
if (md==i) continue;
if (adj[md][i]==0){
hub=i;
break;
}
}
for (int i=0;i<V;i++){
if (adj[hub][i]) bits.emplace_back(i);
}
for (int i=0;i<10;i++){
for (int j=i+1;j<10;j++){
if (adj[bits[i]][bits[j]]){
bitsDeg[bits[i]]++;
bitsDeg[bits[j]]++;
}
}
}
ll s=-1,e=-1;
for (int i=0;i<V;i++){
if (bitsDeg[i]==1 && s==-1) s=i;
else if (bitsDeg[i]==1) e=i;
} //find the start and ends of the chains
if (deg[s]<deg[e]) swap(s,e);
//start at 2^0 to 2^9
ll ptr=s,cnt=0;
m[s]=0,m[e]=9;
vis[s]=true;
while (ptr!=e){
for (int i=0;i<V;i++){
if (i==ptr) continue;
if (bitsDeg[i] && !vis[i] && adj[ptr][i]){
//if is special node and not visited before
//and is adjacents
ptr=i;
break;
}
}
cnt++;
m[ptr]=cnt;
vis[ptr]=true;
}
vis[e]=true;
vis[hub]=true;
vis[md]=true;
for (int i=0;i<V;i++){
if (vis[i]) continue;
if (i==hub || i==md) continue;
//special node
for (int j=0;j<V;j++){
if (i==j) continue;
if (j==hub || j==md) continue;
//same guy
if (adj[i][j]==0) continue;
//no edge
if (vis[j]==0) continue;
//is not a special node
idx[i]+=(1<<m[j]);
}
}
ll ed=0;
for (int i=0;i<U;i++){
if (vis[C[i]] ||vis[D[i]]) continue;
out[idx[C[i]]].emplace_back(idx[D[i]]);
ed++;
}
InitMap(V-12,ed);
for (int i=0;i<1012;i++){
for (auto u:out[i]){
MakeMap(i,u);
}
}
}
