#include "Alicelib.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
vector<pii> vec;
Loop (i,0,M)
vec.emplace_back(A[i], B[i]);
Loop (i,0,N) Loop (b,0,10)
if ((i>>b)&1)
vec.emplace_back(i, N + b);
Loop (b,0,10)
vec.emplace_back(N + b, N + 10);
Loop (i,0,N+10)
vec.emplace_back(i, N + 11);
Loop (b,1,10)
vec.emplace_back(N + b - 1, N + b);
InitG(N + 12, vec.size());
Loop (i,0,vec.size()) {
auto [x, y] = vec[i];
MakeG(i, x, y);
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
namespace {
struct Eater {
template<class T>
Eater &operator<<(const T &) { return *this; }
} eater;
#define cerr eater
const int N = 1010;
vector<int> A[N];
bool is_new[N];
int num[N];
int n;
array<int, 12> find_bits()
{
int mx = 0;
{
Loop (i,0,n+12)
if (A[mx].size() < A[i].size())
mx = i;
}
int ptr;
{
vector<bool> adj(n + 12);
for (auto v : A[mx])
adj[v] = 1;
adj[mx] = 1;
ptr = 0;
while (adj[ptr])
ptr++;
}
vector<int> path;
{
int beg = -1, end = -1;
set<int> bits(A[ptr].begin(), A[ptr].end());
for (int v : A[ptr]) {
int cnt = 0;
for (int u : A[v])
cnt += bits.count(u);
if (cnt != 1)
continue;
if (beg == -1) {
beg = v;
continue;
}
if (A[beg].size() > A[v].size()) {
end = v;
} else {
end = beg;
beg = v;
}
}
cerr << "beg = " << beg << ", end = " << end << '\n';
cerr << "bits = ";
for (int v : bits)
cerr << v << ", ";
cerr << '\n';
int pre = -1;
path = {beg};
for (int v = beg; v != end;) {
int nxt = -1;
cerr << "v = " << v << '\n';
for (int u : A[v])
if (bits.count(u) && u != pre)
nxt = u;
cerr << "nxt = " << nxt << '\n';
assert(nxt != -1);
path.emplace_back(nxt);
if (path.size() > 10) {
cerr << "bad!\n";
break;
}
pre = v;
v = nxt;
}
}
array<int, 12> ans;
Loop (i,0,10)
ans[i] = path[i];
ans[10] = ptr;
ans[11] = mx;
fill(is_new, is_new + n + 12, false);
for (int v : ans)
is_new[v] = true;
return ans;
}
}
void Bob( int V, int U, int C[], int D[] ){
n = V - 12;
Loop (i,0,U) {
A[C[i]].push_back(D[i]);
A[D[i]].push_back(C[i]);
}
auto bits = find_bits();
Loop (b,0,10) {
for (int v : A[bits[b]])
num[v] |= (1 << b);
}
vector<pii> ans;
Loop (i,0,U) {
int v = C[i], u = D[i];
if (is_new[v] || is_new[u])
continue;
ans.emplace_back(num[v], num[u]);
}
InitMap(n, ans.size());
for (auto [x, y] : ans)
MakeMap(x, y);
}
