#include "Alicelib.h"
#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
using pii=pair<int, int>;
void InitG(int V, int U);
void MakeG(int pos, int C, int D);
void Alice(int N, int M, int A[], int B[])
{
vector<pii> e;
for (int i=0; i<M; i++) e.push_back({A[i], B[i]});
for (int i=0; i<N; i++)
{
for (int j=0; j<10; j++)
{
if ((i>>j)&1)
{
e.push_back({i, N+j});
}
}
}
for (int i=0; i<10; i++)
{
for (int j=i+1; j<10; j++) e.push_back({N+i, N+j});
e.push_back({N+i, N+11});
}
for (int i=0; i<N; i++) e.push_back({i, N+10});
e.push_back({N+10, N+11});
InitG(N+12, e.size());
for (int i=0; i<e.size(); i++)
{
//cerr<<e[i].first<<' '<<e[i].second<<endl;
MakeG(i, e[i].first, e[i].second);
}
}
#include "Boblib.h"
#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
using pii=pair<int, int>;
void InitMap(int N, int M);
void MakeMap(int A, int B);
const int MN=1013;
int deg[MN], rep[MN];
bool f[MN];
void Bob(int V, int U, int C[], int D[])
{
for (int i=0; i<V; i++) deg[i]=rep[i]=f[i]=0;
for (int i=0; i<U; i++)
{
deg[C[i]]++;
deg[D[i]]++;
}
int n=V-12, rt=-1, dum=-1;
for (int i=0; i<U; i++)
{
if (deg[C[i]]==n+1 && deg[D[i]]==11)
{
rt=C[i];
dum=D[i];
break;
}
if (deg[D[i]]==n+1 && deg[C[i]]==11)
{
rt=D[i];
dum=C[i];
break;
}
}
assert(rt!=-1);
//cerr<<rt<<' '<<dum<<endl;
for (int i=0; i<U; i++)
{
if (C[i]==rt && D[i]!=dum)
{
assert(D[i]!=rt);
f[D[i]]=1;
}
if (D[i]==rt && C[i]!=dum)
{
assert(C[i]!=rt);
f[C[i]]=1;
}
}
vector<int> vec;
for (int i=0; i<V; i++) if (!f[i] && i!=rt && i!=dum) vec.push_back(i);
assert(vec.size()==10);
sort(vec.begin(), vec.end(), [](int x, int y) { return deg[x]>deg[y]; });
for (int i=0; i<10; i++) rep[vec[i]]=i;
for (int i=0; i<U; i++)
{
if ((!f[C[i]] && C[i]!=rt && C[i]!=dum) && f[D[i]])
{
assert(!(rep[D[i]]>>rep[C[i]]));
rep[D[i]]^=(1<<rep[C[i]]);
}
if ((!f[D[i]] && D[i]!=rt && D[i]!=dum) && f[C[i]])
{
assert(!(rep[C[i]]>>rep[D[i]]));
rep[C[i]]^=(1<<rep[D[i]]);
}
}
vector<pii> e;
for (int i=0; i<U; i++)
{
if (f[C[i]] && f[D[i]])
{
e.push_back({rep[C[i]], rep[D[i]]});
}
}
InitMap(n, e.size());
for (auto [u, v]:e) MakeMap(u, v);
}
