#include "Alicelib.h"
#include <vector>
using namespace std;
namespace {
vector<pair<int, int> > graph;
}
void Alice(int N, int M, int A[], int B[])
{
int V = N + 12;
for (int i = 0; i < M; ++i) {
graph.push_back({ A[i], B[i] });
}
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < N; ++j) {
if ((j >> i) & 1) graph.push_back({ i + N, j });
}
}
for (int i = 0; i < 10; ++i) graph.push_back({ i + N, 10 + N });
for (int i = 1; i < 10; ++i) graph.push_back({ i - 1 + N, i + N });
for (int i = 0; i < 10 + N; ++i) graph.push_back({ i, 11 + N });
InitG(V, graph.size());
for (int i = 0; i < graph.size(); ++i) {
MakeG(i, graph[i].first, graph[i].second);
}
}
#include "Boblib.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;
map<int, bool> w[mxN];
vector<int> par;
bool vis[mxN];
int spe[mxN], val[mxN];
void Find(int j)
{
par.push_back(j);
spe[j] = 1;
for (ii i : w[j])
{
if (spe[i.fi] == 3)
Find(i.fi);
}
}
void Bob(int n, int m, int a[], int b[])
{
for (int i = 0; i < m; i++)
w[a[i]][b[i]] = w[b[i]][a[i]] = 1;
for (int i = 0; i < n; i++)
{
if (w[i].size() == n - 2)
{
spe[i] = 1;
vis[i] = 1;
for (ii j : w[i])
vis[j.fi] = 1;
}
}
for (int i = 0; i < n; i++)
{
if (!vis[i])
{
spe[i] = 1;
for (ii j : w[i])
spe[j.fi] = 2;
break;
}
}
for (int i = 0; i < m; i++)
{
if (spe[a[i]] >= 2 && spe[b[i]] >= 2)
spe[a[i]] = 3;
}
for (int i = 0; i < n; i++)
{
if (spe[i] == 2)
Find(i);
}
for (int i = 0; i < n; i++)
{
if (spe[i])
continue;
for (int j = 0; j < par.size(); j++)
{
if (w[par[j]][i])
val[i] += 1 << j;
}
}
vector<ii> ans;
for (int i = 0; i < m; i++)
{
if (spe[a[i]] || spe[b[i]])
continue;
ans.push_back({val[a[i]], val[b[i]]});
}
InitMap(n - 12, ans.size());
for (ii i : ans)
MakeMap(i.fi, i.se);
}
