#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
/// 11:18
static vector<pair<int,int>> edges;
static void add_edge(int x, int y)
{
edges.push_back({x, y});
}
void Alice( int N, int M, int A[], int B[] )
{
int S1, S2;
S1 = N+10;
S2 = N+11;
add_edge(S1, S2);
int i, j;
for(i=0; i<M; ++i)
add_edge(A[i], B[i]);
for(i=0; i<N; ++i)
for(j=0; j<10; ++j)
if(i & (1<<j))
add_edge(i, N+j);
for(i=0; i<10; ++i)
{
add_edge(N+i, S1);
add_edge(N+i, S2);
if(i) add_edge(N+i, N+i-1);
}
add_edge(N+1, N+3);
InitG(N+12, edges.size());
int nr = 0;
for(auto it : edges) MakeG(nr++, it.first, it.second);
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
static int n, V, P[1205];
static vector<pair<int,int>> edges;
static vector<vector<int>> v;
static bitset<1205> bad;
static void add_edge(int x, int y)
{
edges.push_back({x, y});
}
bool sortt(vector<int> &p)
{
vector<vector<int>> gr(V);
for(auto it : p)
for(auto it2 : p)
if(find(v[it].begin(), v[it].end(), it2) != v[it].end())
gr[it].push_back(it2);
vector<int> sp;
for(auto it : p)
if(gr[it].size() == 3) sp.push_back(it);
if(sp.size() != 2) return 0;
for(auto it : p)
if(gr[it].size() != 2 && gr[it].size() != 3 && gr[it].size() != 1) return 0;
int node = sp[0];
gr[node].erase(find(gr[node].begin(), gr[node].end(), sp[1]));
node = sp[1];
gr[node].erase(find(gr[node].begin(), gr[node].end(), sp[0]));
vector<int> vec[2];
for(int step = 0; step < 2; ++step)
{
int prv = sp[0];
node = gr[sp[0]][step];
while(gr[node].size() == 2)
{
vec[step].push_back(node);
int prr = node;
node = gr[node][0] ^ gr[node][1] ^ prv;
prv = prr;
}
vec[step].push_back(node);
}
if(vec[0].size() > vec[1].size()) swap(vec[0], vec[1]);
reverse(vec[0].begin(), vec[0].end());
p.clear();
p.insert(p.end(), vec[0].begin(), vec[0].end());
p.insert(p.end(), sp[0]);
p.insert(p.end(), vec[1].begin(), vec[1].end());
return 1;
}
bool Try(int A, int B)
{
if(v[A].size() != 11 || v[B].size() != 11) return 0;
vector<int> p = v[A];
p.erase(find(p.begin(), p.end(), B));
for(auto it : p)
if(find(v[B].begin(), v[B].end(), it) == v[B].end()) return 0;
int sum = 0, i, j;
for(i=0; i<n; ++i)
for(j=0; j<10; ++j)
if(i & (1<<j))
++sum;
sum += 20 + 20;
int sum2 = 0;
for(auto it : p)
sum2 += v[it].size();
if(sum != sum2) return 0;
bad.reset();
edges.clear();
bad[A] = bad[B] = 1;
for(auto it : p) bad[it] = 1;
for(i=0; i<V; ++i)
for(auto it : v[i])
if(!bad[i] && !bad[it] && i < it)
add_edge(i, it);
if(!sortt(p)) return 0;
vector<int> where(V);
for(i=0; i<10; ++i)
where[p[i]] = i;
vector<int> all;
for(i=0; i<V; ++i)
if(!bad[i])
{
P[i] = 0;
for(auto it : v[i])
if(bad[it])
P[i] ^= (1<<where[it]);
all.push_back(P[i]);
}
sort(all.begin(), all.end());
assert(all.size() == n);
for(i=0; i<n; ++i)
if(all[i] != i) return 0;
InitMap(n, edges.size());
for(auto it : edges)
MakeMap(P[it.first], P[it.second]);
return 1;
}
void Bob( int _V, int U, int C[], int D[] )
{
V = _V;
n = V - 12;
int i;
v.resize(V);
for(i=0; i<U; ++i)
{
v[C[i]].push_back(D[i]);
v[D[i]].push_back(C[i]);
}
for(i=0; i<V; ++i)
for(auto it : v[i])
if(Try(i, it)) return;
}
