#include "Alicelib.h"
#include<bits/stdc++.h>
#define rep(a,b,c) for(ll a=b;a<=c;++a)
#define ll long long
#define ff first
#define ss second
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
static const ll N=1005,inf=1e18;
static int n,m;
static vector<pii> edge;
void Alice( int NN, int MM, int A[], int B[] ){
n=NN,m=MM;
rep(i,0,n+9) edge.push_back(mp(n+11,i));
rep(i,n,n+9) edge.push_back(mp(n+10,i));
rep(i,n,n+8) edge.push_back(mp(i,i+1));
rep(i,0,m-1) edge.push_back(mp(A[i],B[i]));
rep(i,0,n-1) rep(j,0,9) if((i>>j)&1LL) edge.push_back(mp(i,n+j));
InitG(n+12,(int)edge.size());
rep(i,0,(int)edge.size()-1) MakeG(i,edge[i].ff,edge[i].ss);
}
#include "Boblib.h"
#include<bits/stdc++.h>
#define rep(a,b,c) for(ll a=b;a<=c;++a)
#define ll long long
#define ff first
#define ss second
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
static const ll N=1025,inf=1e18;
static int n,m,deg[N],G[N][N],X[15],F[N];
static vector<pii> edge;
static vector<int> adj[N],SP;
static bitset<N> used,ex,head;
static void build(){
rep(i,0,n-1) if(deg[i]==n-2){
rep(j,0,n-1) if(j!=i&&!G[i][j]){
for(int x:adj[j]) SP.push_back(x),ex[x]=1;
for(int x:adj[j]){
for(int v:adj[x]){
if(ex[v]){
head[x]=!head[x];
}
}
}
ex[i]=ex[j]=1;
}
}
assert(!SP.empty());
sort(SP.begin(),SP.end(),[](int a,int b){
if(head[a]==head[b]) return deg[a]>deg[b];
return head[a]>head[b];
});
X[0]=SP.front();used[X[0]]=1;
queue<int> Q;
Q.push(X[0]);
int cnt=0;
while(!Q.empty()){
ll u=Q.front();
Q.pop();
rep(i,0,(int)SP.size()-1) if(!used[SP[i]]){
if(G[u][SP[i]]){
Q.push(SP[i]);
used[SP[i]]=1;
X[++cnt]=SP[i];
break;
}
}
}
}
void Bob( int V, int U, int C[], int D[] ){
n=V;m=U;
rep(i,0,m-1){
adj[C[i]].push_back(D[i]);
adj[D[i]].push_back(C[i]);
G[C[i]][D[i]]=G[D[i]][C[i]]=1;
}
rep(i,0,n-1) deg[i]=(int)adj[i].size();
build();
rep(i,0,n-1){
if(ex[i]) continue;
rep(j,0,9){
if(G[i][X[j]]){
F[i]+=(1LL<<j);
}
}
}
rep(i,0,m-1) if(!ex[C[i]]&&!ex[D[i]]) edge.push_back(mp(F[C[i]],F[D[i]]));
InitMap(V-12,(int)edge.size());
for(auto o:edge) MakeMap(o.ff,o.ss);
}
