#include "Alicelib.h"
#include <utility>
#include <vector>
void Alice(int n, int m, int *eu, int *ev)
{
std::vector<std::pair<int, int> > edge;
for (int i = 0; i < m; i++)
edge.emplace_back(eu[i], ev[i]);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 10; j++)
{
if (i & (1 << j))
edge.emplace_back(i, n + j);
}
}
for (int i = 0; i < n + 10; i++)
edge.emplace_back(i, n + 10);
for (int i = 0; i < 10; i++)
edge.emplace_back(n + i, n + 11);
for (int i = 1; i < 10; i++)
edge.emplace_back(n + i - 1, n + i);
edge.emplace_back(n + 1, n + 3);
InitG(n + 12, edge.size());
for (int i = 0; i < edge.size(); i++)
MakeG(i, edge[i].first, edge[i].second);
}
#include "Boblib.h"
#include <algorithm>
#include <utility>
#include <vector>
std::vector<int> adj[2005], G[2005], seq;
int real[2005];
bool del[2005];
inline bool have_edge(int u, int v) { return std::binary_search(adj[u].begin(), adj[u].end(), v); }
void dfs(int u, int dep = 0, int fa = -1)
{
seq[dep] = u;
for (int v : G[u])
{
if (v != fa)
dfs(v, dep + 1, u);
}
}
void Bob(int n, int m, int *eu, int *ev)
{
for (int i = 0; i < m; i++)
{
adj[eu[i]].push_back(ev[i]);
adj[ev[i]].push_back(eu[i]);
}
for (int i = 0; i < n; i++)
std::sort(adj[i].begin(), adj[i].end());
int n10 = -1;
for (int i = 0; i < n; i++)
{
if (adj[i].size() == n - 2)
n10 = i;
}
int n11 = -1;
for (int i = 0; i < n; i++)
{
if (i != n10 && !have_edge(n10, i))
n11 = i;
}
seq = adj[n11];
for (int u : seq)
{
for (int v : seq)
{
if (have_edge(u, v))
G[u].push_back(v);
}
}
int n0 = -1;
for (int u : seq)
{
if (G[u].size() == 1 && G[G[u][0]].size() == 3)
n0 = u;
}
for (int u : seq)
{
if (G[u].size() != 3)
continue;
for (int v : G[u])
{
if (G[v].size() != 3)
continue;
G[u].erase(std::lower_bound(G[u].begin(), G[u].end(), v));
G[v].erase(std::lower_bound(G[v].begin(), G[v].end(), u));
}
}
dfs(n0);
for (int u : seq)
del[u] = true;
del[n10] = del[n11] = true;
for (int i = 0; i < n; i++)
{
if (del[i])
continue;
int rk = 0;
for (int j = 0; j < 10; j++)
{
if (have_edge(i, seq[j]))
rk |= 1 << j;
}
real[rk] = i;
}
std::vector<std::pair<int, int> > edge;
for (int i = 0; i < n - 12; i++)
{
for (int j = 0; j < i; j++)
{
if (have_edge(real[i], real[j]))
edge.emplace_back(i, j);
}
}
InitMap(n - 12, edge.size());
for (int i = 0; i < edge.size(); i++)
MakeMap(edge[i].first, edge[i].second);
}
