#include "Alicelib.h"
#include <cassert>
#include <cstdio>
void Alice( int N, int M, int A[], int B[] );
void InitG( int V, int U );
void MakeG( int pos, int C, int D );
void Alice( int N, int M, int A[], int B[] ){
int V=N+12,U=M;
for(int i=0;i<N;i++){
for(int j=0;j<10;j++){
if(i&(1<<j))
U++;
}
// U++;
}
for(int j=0;j<9;j++) U++,U++,U++;
U++;U++;
InitG(V,U);
U=0;
for(int i=0;i<N;i++){
for(int j=0;j<10;j++){
if(i&(1<<j))
MakeG(U++,i,N+j);
}
// MakeG(U++,i,N+10);
}
for(int i=0;i<M;i++) MakeG(U++,A[i],B[i]);
for(int j=0;j<10;j++) MakeG(U++,N+j,N+10);
MakeG(U++,N+10,N+11);
for(int j=0;j<9;j++)
MakeG(U++,N+j,N+j+1);
for(int j=1;j<10;j++) MakeG(U++,N+j,N+11);
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
void Bob( int V, int U, int C[], int D[] ){
int N=V-12;
int M=U;
for(int i=0;i<N;i++){
for(int j=0;j<10;j++){
if(i&(1<<j)) M--;
}
// M--;
}
// debug()<<imie(N);
// for(int i=0;i<M;i++) debug()<<imie(C[i])imie(D[i]);
for(int j=0;j<9;j++) M--,M--,M--;
M--;M--;
InitMap(N,M);
// vec<bool> bad(V,1);
vec<vec<int>>g(V,vec<int>());
for(int i=0;i<U;i++)
g[C[i]].pb(D[i]),g[D[i]].pb(C[i]);
int cnt=0;
vec<int>obr(V,0);
// debug()<<imie(N);
vec<bool>rbad;
for(int i=0;i<V;i++){
// deb
if(sz(g[i])==11){
// debug()<<imie(i)imie(g[i]);
/// should be the main
vec<bool> bad(V,0);
for(auto &u : g[i]) bad[u]=1;
bad[i]=0;
vec<int>path;vec<int>they;
vec<vec<int>>how(12,vec<int>());
for(int v=0;v<V;v++){
if(bad[v]){
they.pb(v);
for(auto &u : g[v]){
if(bad[u]) how[sz(they)-1].pb(u);
}
}
}
// debug()<<imie(i)imie(sz(they));
if(sz(they)!=11) continue;
cnt++;///i'm sure that it's main
vec<bool>start(11,1);
// debug()<<imie(i)imie(they);
int kk=0;
int sh=-1;
int root=i;
for(int i=0;i<sz(they);i++){
int v=they[i];
// debug()<<imie(meimie(how[i]);
sort(all(g[v]));sort(all(how[i]));
vec<int> me=g[v];me.erase(find(all(me),root),find(all(me),root)+1);
// debug()<<imie(me)imie(how[i]);
if(how[i]==me && sz(me)==9){
if(kk){
kk=0;
break;
}
for(auto &u : g[v]){
start[find(all(they),u)-they.begin()]=0;
}
// for(auto &u : g[v]){
// g[u].erase(find(all(g[u]),v),find(all(g[u]),v)+1);
// }
sh=v;
start[i]=0;
kk=1;
// if(kk)
// debug()<<imie(kk);
// break;
}
}
if(!kk) continue;
// debug()<<imie(they)imie(start);
for(int i=0;i<sz(they);i++){
if(start[i]){
path.pb(they[i]);
for(int j=0;j<10;j++){
int v=path.back();
// debug()<<imie(v)imie(bad[15])imie(g[v]);
for(auto &u : g[v]){
if(u==sh) continue;
if(bad[u] && (sz(path)==1 || path[sz(path)-2]!=u)){
path.pb(u);
break;
}
}
}
// debug()<<imie(path);
}
}
vec<bool>u(V,0);
for(auto &z : path){
if(u[z]) kk=0;
u[z]=1;
// if(u[z])
}
if(!kk || sz(path)!=10) continue;
// debug()<<imie(path);
for(int j=0;j<10;j++){
// debug()<<imie(j)imie(path[j])imie(g[path[j]]);
for(auto &u : g[path[j]]){
if(!bad[u]){
// debug()<<imie(path[j])imie(g[path[j]]);
obr[u]+=(1<<j);
}
}
}
rbad=bad;
rbad[i]=1;
break;
}
}
// debug()<<imie(obr);
for(int i=0;i<U;i++){
if(rbad[C[i]] || rbad[D[i]]) continue;
MakeMap(obr[C[i]],obr[D[i]]);
}
}
