#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include "bits/stdc++.h"
using namespace std;
static const int N = 1500, L = 9, R = 10, M = 2;
static int n, m;
static vector<pair<int, int>> e;
void Alice(int _n, int _m, int A[], int B[]) {
n = _n, m = _m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < R; j++) {
if ((i >> j) & 1) e.push_back({i, n + 1 + L + j});
}
}
for (int i = 0; i < m; i++) e.push_back({A[i], B[i]});
for (int i = 0; i < n; i++) e.push_back({i, n});
for (int i = n + 1; i < n + L + 1; i++) e.push_back({i, n});
e.push_back({n, n + L + 1});
for (int i = n + L + 1; i < n + L + 1 + R - 1; i++) e.push_back({i, i + 1});
for (int i = n + 1; i < n + 1 + M; i++) {
for (int j = n + L + 1; j < n + L + 1 + R; j++) {
e.push_back({i, j});
}
}
InitG(n + 1 + L + R, e.size());
for (int i = 0; i < e.size(); i++) MakeG(i, e[i].first, e[i].second);
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include "bits/stdc++.h"
using namespace std;
static const int N = 1500, L = 9, R = 10, M = 2;
static int n, m, p[N], cnt[N], used[N];
static vector<pair<int, int>> e;
static vector<int> g[N];
static map<vector<int>, int> ma;
void Bob(int V, int U, int C[], int D[]) {
n = V - 1 - L - R;
if (n == 1) {
InitMap(1, 0);
return;
}
if (n == 2) {
if (U == 42) {
InitMap(2, 0);
} else {
InitMap(2, 1);
MakeMap(0, 1);
}
return;
}
for (int i = 0; i < U; i++) {
int u = C[i], v = D[i];
g[u].push_back(v);
g[v].push_back(u);
cnt[u]++;
cnt[v]++;
}
int s = max_element(cnt, cnt + V) - cnt;
p[s] = -1;
for (auto x: g[s]) {
if (cnt[x] != R + 1) continue;
vector<int> a;
for (auto y: g[x]) {
if (y == s) continue;
a.push_back(y);
}
sort(a.begin(), a.end());
ma[a]++;
}
vector<int> a;
for (auto [b, cn]: ma) {
if (a.size() && cn == M) assert(0);
if (cn == M) a = b;
}
vector<int> pt;
int v = s;
for (int _ = 0; _ < R; _++) {
for (auto x: g[v]) {
if (find(a.begin(), a.end(), x) != a.end() && !used[x]) {
used[v] = 1;
v = x;
pt.push_back(v);
break;
}
}
}
for (int i = 0; i < V; i++) {
if (i == s) continue;
int id = 0;
for (auto x: g[i]) {
if (find(pt.begin(), pt.end(), x) != pt.end()) {
id += 1 << (find(pt.begin(), pt.end(), x) - pt.begin());
}
}
if (id < n && find(pt.begin(), pt.end(), i) == pt.end()) p[i] = id;
else p[i] = -1;
}
for (int i = 0; i < V; i++) {
if (p[i] == -1) continue;
for (auto x: g[i]) {
if (p[x] == -1) continue;
if (p[x] < p[i]) continue;
e.push_back({p[i], p[x]});
}
}
InitMap(n, e.size());
for (auto [u, w]: e) MakeMap(u, w);
}
