#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
void Alice(int N, int M, int A[], int B[]){
vector<vector<int> > adj(N+12);
int cnt = M;
for (int i = 0; i < M; i++)
adj[A[i]].emplace_back(B[i]);
for (int i = N; i < N+10 - 1; i++) {
adj[i].emplace_back(i+1);
++cnt;
}
for (int i = 0; i < N; i++)
for (int j = 0; j < 10; j++) if (i>>j&1) {
adj[N+j].emplace_back(i);
++cnt;
}
for (int i = 0; i < N; i++) {
adj[N+10].emplace_back(i);
++cnt;
}
adj[N+10].emplace_back(N+11);
++cnt;
InitG(N+12, cnt);
cnt = 0;
for (int i = 0; i < N+12; i++)
for (int j : adj[i]) MakeG(cnt++, i, j);
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
void Bob( int V, int U, int C[], int D[] ){
if (V-12 == 1) {
InitMap(1, 0);
return;
}
vector<vector<int> > adj(V, vector<int>(V, 0));
vector<int> deg(V, 0);
for (int i = 0; i < U; i++) {
++deg[C[i]]; ++deg[D[i]];
adj[C[i]][D[i]] = adj[D[i]][C[i]] = 1;
}
int p1 = -1, p2 = -1;
for (int i = 0; i < V; i++) if (deg[i] == V-11) p1 = i;
for (int i = 0; i < V; i++)
if (deg[i] == 1 && adj[p1][i]) p2 = i;
vector<int> old_graph;
int start_of_chain = -1;
for (int i = 0; i < V; i++)
if (adj[p1][i] && i != p2) {
old_graph.emplace_back(i);
} else if (!adj[p1][i] && deg[i] == 1) start_of_chain = i;
int old = -1;
vector<int> chain(1, start_of_chain);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < V; j++) if (j != old && adj[start_of_chain][j] && !adj[p1][j]) {
old = start_of_chain;
start_of_chain = j;
chain.emplace_back(j);
break;
}
}
if (deg[chain[0]] < deg[chain.back()]) reverse(chain.begin(), chain.end());
vector<pair<int, int> > edges;
for (int i = 0; i < U; i++) {
int a = C[i], b = D[i];
if (adj[p1][a] && a != p2 && adj[p1][b] && b != p2) {
int m1 = 0, m2 = 0;
for (int j = 0; j < 10; j++) if (adj[chain[j]][a]) m1 += (1<<j);
for (int j = 0; j < 10; j++) if (adj[chain[j]][b]) m2 += (1<<j);
edges.emplace_back(m1, m2);
}
}
InitMap(old_graph.size(), edges.size());
for (int i = 0; i < edges.size(); i++) MakeMap(edges[i].first, edges[i].second);
}
/*
4 3
0 1
0 2
0 3
*/
