#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
void Alice(int N, int M, int A[], int B[])
{
if (N == 1)
{
InitG(1, 0);
return;
}
vector<pair<int, int>> edges;
for (size_t i = 0; i < M; ++i)
edges.emplace_back(A[i], B[i]);
for (size_t i = 0; i < N; ++i)
for (size_t j = 0; j < 10; ++j)
if (i & (1 << j))
edges.emplace_back(i, N + j);
for (size_t i = 0; i < 10; ++i)
{
edges.emplace_back(N + i, N + 10);
if (i < 9)
edges.emplace_back(N + i, N + i + 1);
if (i)
edges.emplace_back(N + i, N + 11);
}
InitG(N + 12, edges.size());
for (size_t i = 0; i < edges.size(); ++i)
MakeG(i, edges[i].first, edges[i].second);
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
void Bob(int V, int U, int C[], int D[])
{
if (V == 1)
{
InitMap(1, 0);
return;
}
vector<vector<int>> G(V);
for (size_t i = 0; i < U; ++i)
G[C[i]].push_back(D[i]), G[D[i]].push_back(C[i]);
int x = -1, y = -1;
vector<int> d(V);
for (size_t i = 0; i < V; ++i)
if (G[i].size() == 10)
{
fill(d.begin(), d.end(), 0);
int e[2] = {0, 0};
bool possible = 1;
for (auto const &j : G[i])
{
for (auto const &v : G[j])
if (find(G[i].begin(), G[i].end(), v) != G[i].end())
d[j]++;
if (d[j] != 1 && d[j] != 2)
{
possible = 0;
break;
}
e[d[j] - 1]++;
}
if (!possible || e[0] != 2 || e[1] != 8)
continue;
x = i;
break;
}
vector<int> bit_vertices;
for (size_t i = 0; i < V; ++i)
if (G[i].size() == 9)
{
int v0 = -1;
bool possible = 1;
for (auto const &j : G[x])
if (find(G[i].begin(), G[i].end(), j) == G[i].end())
{
if (v0 != -1)
possible = 0;
v0 = j;
}
if (v0 == -1 || !possible || d[v0] != 1)
continue;
bit_vertices.clear();
bit_vertices.push_back(v0);
int last = -1;
for (size_t k = 0; k < 9; ++k)
{
int v1 = -1;
for (auto const &j : G[v0])
if (j != last && find(G[i].begin(), G[i].end(), j) != G[i].end())
{
if (v1 != -1)
possible = 0;
v1 = j;
}
if (v1 == -1)
{
possible = 0;
break;
}
last = v0;
v0 = v1;
bit_vertices.push_back(v0);
}
if (!possible || bit_vertices.size() != 10)
continue;
y = i;
break;
}
vector<int> p(V);
for (size_t i = 0; i < V; ++i)
if (i != x && i != y && find(bit_vertices.begin(), bit_vertices.end(), i) == bit_vertices.end())
for (auto const &v : G[i])
{
size_t const k = find(bit_vertices.begin(), bit_vertices.end(), v) - bit_vertices.begin();
if (k != 10)
p[i] |= 1 << k;
}
vector<pair<int, int>> edges;
for (size_t i = 0; i < V; ++i)
if (i != x && i != y && find(bit_vertices.begin(), bit_vertices.end(), i) == bit_vertices.end())
for (auto const &v : G[i])
if (find(bit_vertices.begin(), bit_vertices.end(), v) == bit_vertices.end() && i < v)
edges.emplace_back(p[i], p[v]);
InitMap(V - 12, edges.size());
for (auto const &[u, v] : edges)
MakeMap(u, v);
}
