#include "Alicelib.h"
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
int re[1024];
vector<pii> edg;
void Alice (int N, int M, int A[], int B[]) {
for(int i=0;i<M;i++) {
edg.push_back({A[i], B[i]});
}
for(int i=0,j=0;i<1000;i++,j++) {
while(__builtin_popcount(j) >= 9) j++;
re[i] = j;
}
for(int i=0;i<10;i++) {
if(i) edg.push_back({N+i-1, N+i});
for(int j=0;j<N;j++) {
if((1<<i) & re[j]) edg.push_back({N+i, j});
}
}
for(int i=0;i<N;i++) {
edg.push_back({N+10, i});
}
for(int i=0;i<N+10;i++) {
edg.push_back({N+11, i});
}
InitG(N+12, edg.size());
for(int i=0;i<(int)edg.size();i++) {
int A, B;
tie(A, B) = edg[i];
MakeG(i, A, B);
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
int idx[1024], rev[1024];
bool chk[1024];
vector<int> adj[1024], oth[1024], ep, line;
vector<pii> ans;
void Bob( int V, int U, int C[], int D[] ){
for(int i=0;i<U;i++) {
adj[C[i]].push_back(D[i]);
adj[D[i]].push_back(C[i]);
}
int VA = 0, VB = V*(V-1)/2;
for(int i=0;i<V;i++) {
if(adj[i].size() > adj[VA].size()) VA = i;
}
chk[VA] = true;
VB -= VA;
for(auto &T : adj[VA]) {
VB -= T;
}
chk[VB] = true;
for(auto &T : adj[VB]) {
chk[T] = true;
}
for(int i=0;i<V;i++) {
if(chk[i]) continue;
for(auto &T : adj[i]) {
if(!chk[T]) oth[i].push_back(T);
}
if(oth[i].size() == 1) ep.push_back(i);
}
if(adj[ep[0]].size() < adj[ep[1]].size()) {
swap(ep[0], ep[1]);
}
for(int i=ep[0],j=-1;;) {
line.push_back(i);
if(~j && oth[i].size() == 1) break;
for(auto &T : oth[i]) {
if(T != j) {
j = i;
i = T;
break;
}
}
}
chk[VA] = false;
chk[VB] = false;
for(int i=0;i<10;i++) {
for(auto &T : adj[line[i]]) {
if(chk[T]) idx[T] += (1<<i);
}
}
for(int i=0,j=0;i<1000;i++,j++) {
while(__builtin_popcount(j) >= 9) j++;
rev[j] = i;
}
for(int i=0;i<U;i++) {
if(!chk[C[i]] || !chk[D[i]]) continue;
ans.push_back({rev[idx[C[i]]], rev[idx[D[i]]]});
}
InitMap(V-12, ans.size());
for(auto &T : ans) {
MakeMap(T.X, T.Y);
}
}
