#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e3 + 20;
vector<ii> ed;
void Alice(int n, int m, int a[], int b[])
{
for (int i = 0; i < m; i++)
ed.push_back({a[i], b[i]});
for (int j = 0; j < 10; j++)
{
for (int i = 0; i < n; i++)
{
if ((i >> j) & 1)
ed.push_back({i, n + j});
}
ed.push_back({n + j, n + 10});
if (j)
ed.push_back({n + j, n + j - 1});
}
for (int i = 0; i < n + 10; i++)
ed.push_back({n + 11, i});
InitG(n + 12, ed.size());
m = 0;
for (ii i : ed)
MakeG(m++, i.fi, i.se);
}
#include "Boblib.h"
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
namespace {
vector<int> graph[2000];
bool mark[2000];
int id[2000];
}
void Bob(int V, int U, int C[], int D[])
{
for (int i = 0; i < U; ++i) {
graph[C[i]].push_back(D[i]);
graph[D[i]].push_back(C[i]);
}
pair<int, int> mxdeg{ -1, -1 };
for (int i = 0; i < V; ++i) mxdeg = max(mxdeg, { graph[i].size(), i });
int s = mxdeg.second;
int w = V * (V - 1) / 2 - s;
for (int u : graph[s]) w -= u;
for (int i = 0; i < V; ++i) mark[i] = false;
for (int u : graph[w]) mark[u] = true;
vector<int> marker;
int p = -1, ori = -1;
for (int i = 0; i < V; ++i) if (mark[i]) {
int d = 0, nx = 0;
for (int j : graph[i]) if (mark[j]) {
++d;
nx = j;
}
if (d == 1) {
p = nx;
ori = i;
break;
}
}
assert(p != -1);
marker.push_back(ori);
for (;;) {
marker.push_back(p);
bool found = false;
for (int q : graph[p]) if (mark[q] && q != ori) {
ori = p;
p = q;
found = true;
break;
}
if (!found) break;
}
if (graph[marker[0]].size() < graph[marker[marker.size() - 1]].size()) {
reverse(marker.begin(), marker.end());
}
for (int i = 0; i < V; ++i) id[i] = 0;
for (int i = 0; i < marker.size(); ++i) {
for (int j : graph[marker[i]]) {
id[j] |= 1 << i;
}
}
mark[s] = mark[w] = true;
vector<pair<int, int> > ans;
for (int i = 0; i < V; ++i) if (!mark[i]) {
for (int j : graph[i]) if (i < j && !mark[j]) {
ans.push_back({ id[i], id[j] });
}
}
InitMap(V - 12, ans.size());
for (auto e : ans) MakeMap(e.first, e.second);
}
