#include <bits/stdc++.h>
#include <cassert>
#include <cstdio>
#include "Alicelib.h"
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
vector<array<int, 2>> v;
for(int i = 0; i < M; i++)
{
v.push_back({A[i], B[i]});
}
for(int i = 0; i < N; i++)
{
for(int j = 0; j < 10; j++)
{
if((1ll << j)&i) v.push_back({N+j, i});
}
v.push_back({N+10, i});
v.push_back({N+11, i});
}
for(int i = 0; i < 10; i++)
{
v.push_back({N+10, N+i});
if(i) v.push_back({N+i-1, N+i});
}
InitG(N+12, v.size());
for(int i = 0; i < v.size(); i++)
{
MakeG(i, v[i][0], v[i][1]);
}
}
#include <bits/stdc++.h>
#include <cassert>
#include <cstdio>
#include "Boblib.h"
using namespace std;
void Bob( int V, int U, int C[], int D[] ){
int N = V-12;
vector<int> deg(V), loc(V);
vector<set<int>>adj(V);
vector<array<int, 2>> nodes(V);
int mxm = 0;
for(int i = 0; i < U; i++)
{
deg[C[i]]++;
deg[D[i]]++;
adj[C[i]].insert(D[i]);
adj[D[i]].insert(C[i]);
}
for(int i = 0; i < V; i++)
{
nodes[i][1] = i;
loc[i] = i;
if(deg[mxm] < deg[i]) mxm = i;
}
nodes[mxm][0] = N+10;
for(int i = 0; i < V; i++)
{
if(mxm == i) continue;
if(adj[mxm].find(i) == adj[mxm].end())
{
nodes[loc[i]][0] = N+11;
}
}
sort(nodes.begin(), nodes.end());
for(int i = 0; i < V; i++)
{
loc[nodes[i][1]] = i;
}
int cur = -1;
for(int i = 0; i < V-2; i++)
{
if(adj[nodes[N+11][1]].find(nodes[i][1]) != adj[nodes[N+11][1]].end()) continue;
if(nodes[i][0]) continue;
if(cur == -1 || deg[cur] > deg[nodes[i][1]])
{
cur = nodes[i][1];
}
}
vector<array<int, 2>> v;
int cnt = N+9;
while(cnt >= N)
{
nodes[loc[cur]][0] = cnt;
for(auto it : adj[cur])
{
if(nodes[loc[it]][0]) continue;
if(adj[nodes[N+11][1]].find(it) != adj[nodes[N+11][1]].end()) continue;
cur = it;
break;
}
cnt--;
}
sort(nodes.begin(), nodes.end());
for(int i = 0; i < V; i++)
{
loc[nodes[i][1]] = i;
}
for(int i = 0; i < N; i++)
{
for(int j = 0; j < 10; j++)
{
if(adj[nodes[i][1]].find(nodes[N+j][1]) != adj[nodes[i][1]].end())
{
nodes[i][0] |= (1ll << j);
}
}
}
sort(nodes.begin(), nodes.end());
for(int i = 0; i < V; i++)
{
loc[nodes[i][1]] = i;
}
for(int i = 0; i < U; i++)
{
if(nodes[loc[C[i]]][0] >= N || nodes[loc[D[i]]][0] >= N) continue;
v.push_back({nodes[loc[C[i]]][0], nodes[loc[D[i]]][0]});
}
InitMap(N, v.size());
for(auto [a, b] : v) MakeMap(a, b);
}
