#include "Alicelib.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
void Alice(int N, int M, int A[], int B[]) {
InitG(2 * N + 2, M + (N + 2) * (N + 1) / 2 + N * (N + 1) / 2);
int ptr = 0;
for (int i = 0; i < M; i++) {
MakeG(ptr++, A[i], B[i]);
}
for (int i = N + 1; i <= 2 * N + 2; i++) {
for (int j = i + 1; j <= 2 * N + 2; j++) {
MakeG(ptr++, i - 1, j - 1);
}
}
for (int i = 0; i < N; i++) {
for (int j = N; j <= N + i; j++) {
MakeG(ptr++, i, j);
}
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
void dfs(int v, vector<bool> &used, vector<int> &comp, vector<vector<int>> &g) {
comp.pb(v);
used[v] = true;
for (auto u : g[v]) {
if (!used[u]) {
dfs(u, used, comp, g);
}
}
}
vector<int> get_clique(vector<int> &have, vector<vector<bool>> &ok) {
vector<int> rez;
for (int mask = 1; mask < (1 << (SZ(have))); mask++) {
bool can = true;
for (int i = 0; i < SZ(have); i++) {
if ((mask >> i) & 1) {
int v = have[i];
for (int j = i + 1; j < SZ(have); j++) {
if ((mask >> j) & 1) {
int u = have[j];
if (!ok[u][v]) {
can = false;
}
}
}
}
}
if (can && __builtin_popcount(mask) > SZ(rez)) {
rez = {};
for (int i = 0; i < SZ(have); i++) {
if ((mask >> i) & 1) {
rez.pb(have[i]);
}
}
}
}
return rez;
}
void Bob(int V, int U, int C[], int D[]) {
vector<bool> used(V);
vector<vector<int>> g(V);
vector<vector<bool>> ok(V, vector<bool>(V));
for (int i = 0; i < U; i++) {
g[C[i]].pb(D[i]);
g[D[i]].pb(C[i]);
ok[C[i]][D[i]] = ok[D[i]][C[i]] = true;
}
vector<int> comp, cl;
for (int i = 0; i < V; i++) {
if (!used[i]) {
comp = {};
dfs(i, used, comp, g);
vector<int> rez = get_clique(comp, ok);
if (SZ(rez) > SZ(cl)) {
cl = rez;
}
}
}
InitMap(V - SZ(cl), U - SZ(cl) * (SZ(cl) - 1) / 2 - (V - SZ(cl)) * (V - SZ(cl) + 1) / 2);
vector<bool> in_clique(V);
for (auto it : cl) {
in_clique[it] = true;
}
vector<int> id(V + 1);
for (int i = 0; i < V; i++) {
if (!in_clique[i]) {
int cnt = 0;
for (auto u : g[i]) {
if (in_clique[u]) {
cnt++;
}
}
id[i] = cnt;
}
}
for (int v = 0; v < V; v++) {
for (int u : g[v]) {
if (id[v] && id[u] && id[v] < id[u]) {
//cerr << id[v] << ' ' << id[u] << endl;
MakeMap(id[v] - 1, id[u] - 1);
}
}
}
}
