#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>arestas;
void Alice( int n, int m, int A[], int B[] ){
int sb=0, cnt=0;
for(int i=0;i<n;i++)
for(int k=0;k<10;k++) if(i&(1<<k)) sb++;
InitG(n+13,m+n+11+sb+9+9);
for(int i=0;i<m;i++) MakeG(cnt++,A[i],B[i]);
for(int i=0;i<=n+10;i++) if(i!=n) MakeG(cnt++,n,i);
//for(int i=n+1;i<=n+10;i++) MakeG(cnt++,n+11,i);
MakeG(cnt++,n+11,n+1);
for(int i=0;i<n;i++)
for(int k=0;k<10;k++) if(i&(1<<k)) MakeG(cnt++,i,n+k+1);
for(int i=n+2;i<=n+10;i++){
MakeG(cnt++,i-1,i);
MakeG(cnt++,n+12,i);
}
}
#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1020;
vector<int>v[maxn];
int val[maxn], marc[maxn], freq[maxn];
int arestas[maxn][maxn];
void Bob( int N, int M, int C[], int D[] ){
for(int i=0;i<M;i++){
arestas[C[i]][D[i]]=arestas[D[i]][C[i]]=1;
v[C[i]].push_back(D[i]);
v[D[i]].push_back(C[i]);
}
int n=N-13;
int sb=0;
for(int i=0;i<n;i++)
for(int k=0;k<10;k++) if(i&(1<<k)) sb++;
int m=M-n-11-sb-9-9;
InitMap(n,m);
int pai;
for(int i=0;i<N;i++){
sort(v[i].begin(),v[i].end());
//cout << i << " " << v[i].size() << ": ";
//for(int x : v[i]) cout << x << " ";
//cout << endl;
if(v[i].size()==N-3) pai=i;
}
//cout << endl;
//cout << "! " << pai << endl;
v[pai].push_back(maxn);
int especial, maluco;
for(int i=0;i<N;i++){
int aux=lower_bound(v[pai].begin(),v[pai].end(),i)-v[pai].begin();
if(v[pai][aux]!=i&&i!=pai&&v[i].size()==1) especial=i;
else if(v[pai][aux]!=i&&i!=pai) maluco=i;
}
for(int x : v[maluco]) freq[x]++;
//cout << "!! " << especial << endl;
int at=v[especial][0];
marc[especial]++; marc[pai]++;
for(int i=0;i<10;i++){
marc[at]++;
for(int x : v[at]) val[x]|=(1<<i);
int nxt;
for(int viz : v[at]){
if(!marc[viz]&&freq[viz]) nxt=viz;
}
at=nxt;
}
for(int i=0;i<N;i++){
if(marc[i]) continue;
for(int x : v[i]) if(x>i&&marc[x]==0) MakeMap(val[x],val[i]);
}
}
