#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;
}
const int N = 80;
bitset<N> a[N];
int n, need;
vector<int> ans;
mt19937 rnd(228);
void rec(bitset<N> can_take, bitset<N> take) {
if (SZ(ans) == need) {
return;
}
if (!can_take.count()) {
if (take.count() > SZ(ans)) {
ans = {};
for (int i = 0; i < n; i++) {
if (take[i]) {
ans.pb(i);
}
}
}
return;
}
if (can_take.count() + take.count() <= SZ(ans)) {
return;
}
pair<int, int> v = {-1, -1};
for (int i = 0; i < n; i++) {
if (can_take[i]) {
int x = (a[i] & can_take).count();
if (x < 2) {
take[i] = 1;
can_take[i] = 0;
can_take ^= (can_take & a[i]);
rec(can_take, take);
return;
}
v = max(v, make_pair(x, i));
}
}
can_take[v.S] = 0;
take[v.S] = 1;
rec(can_take ^ (can_take & a[v.S]), take);
take[v.S] = 0;
rec(can_take, take);
take[v.S] = 0;
can_take[v.S] = 1;
}
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;
}
n = V;
need = V / 2 + 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
if (ok[i][j]) {
a[i][j] = 0;
}
else {
a[i][j] = 1;
}
}
}
}
bitset<N> can_take, take;
for (int i = 0; i < n; i++) {
can_take[i] = 1;
}
rec(can_take, take);
vector<int> cl = ans;
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]) {
MakeMap(id[v] - 1, id[u] - 1);
}
}
}
}
