#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
void Alice( int n, int m, int A[], int B[] ){
int cnt = 0;
vector<int> nums;
for(int i = 0;i < 1024;i++){
int bits = 0;
for(int j = 1;j < 1024;j *= 2){
if((i & j) != 0) bits++;
}
if(bits >= 2){
nums.push_back(i);
}
if(nums.size() == n) break;
}
typedef pair<int,int> ii;
vector<ii> edges;
for(int i = 0;i < m;i++){
edges.push_back(ii(A[i],B[i]));
}
int x = n+10;
int y = n+11;
int anchor[10];
for(int i = 0;i < 10;i++) anchor[i] = n+i;
edges.push_back(ii(x,y));
for(int i = 0;i < 10;i++){
edges.push_back(ii(y,anchor[i]));
}
for(int i = 1;i < 9;i++){
edges.push_back(ii(anchor[0],anchor[i]));
edges.push_back(ii(anchor[i],anchor[i+1]));
}
for(int i = 0;i < n;i++){
int k = nums[i];
for(int j = 0;j < 10;j++){
if((k & (1 << j)) != 0){
edges.push_back(ii(i,anchor[j]));
}
}
}
/*
for(ii x : edges){
cout << x.first << " " << x.second << "\n";
}
//*/
InitG(n+12,edges.size());
for(int i = 0;i < edges.size();i++){
MakeG(i,edges[i].first,edges[i].second);
}
//cout << "\n\n";
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
void Bob( int n, int m, int C[], int D[] ){
int on = n - 12;
vector<int> nums;
typedef pair<int,int> ii;
set<ii> edges;
for(int i = 0;i < 1024;i++){
int bits = 0;
for(int j = 1;j < 1024;j *= 2){
if((i & j) != 0) bits++;
}
if(bits >= 2){
nums.push_back(i);
}
if(nums.size() == on) break;
}
vector<int> adj[n];
for(int i = 0;i < m;i++){
adj[C[i]].push_back(D[i]);
adj[D[i]].push_back(C[i]);
//cout << C[i] << " " << D[i] << "\n";
edges.insert(ii(C[i],D[i]));
edges.insert(ii(D[i],C[i]));
}
if(n > 52) return;
int x, y;
for(int i = 0;i < n;i++){
if(adj[i].size() == 1){
x = i;
y = adj[i][0];
break;
}
}
//cout << x << "\n" << y << "\n";
vector<int> aa;
for(int i = 0;i < n;i++){
if(i == x || i == y){
continue;
}
if(edges.find(ii(i,y)) != edges.end()){
aa.push_back(i);
}
}
set<int> anchorSet;
for(int k : aa){
//cout << k << " ";
anchorSet.insert(k);
}
int anchor[10];
fill(anchor,anchor+10,-1);
for(int i = 0;i < 10;i++){
int cnt = 0;
for(int j = 0;j < 10;j++){
if(edges.find(ii(aa[i],aa[j])) != edges.end()){
cnt++;
}
}
if(cnt == 8){
anchor[0] = aa[i];
}
else if(cnt == 1){
anchor[9] = aa[i];
}
}
int cur = anchor[9];
for(int i = 9;i >= 2;i--){
for(int v : adj[cur]){
if(v != anchor[0] && anchorSet.find(v) != anchorSet.end()){
if(i == 9 || v != anchor[i+1]){
cur = v;
anchor[i-1] = cur;
break;
}
}
}
}
bool extras[n];
int anchorMap[n];
int normalMap[n];
fill(extras,extras+n,false);
//unordered_map<int,int> anchorMap;
//cout << "\n";
for(int i =0 ;i < 10;i++){
//cout << anchor[i] << " ";
extras[anchor[i]] = true;
anchorMap[anchor[i]] = i;
}
extras[x] = true;
extras[y] = true;
//cout << "\n";
//unordered_map<int,int> normalMap;
for(int u = 0;u < n;u++){
int value = 0;
if(extras[u]) continue;
for(int v : adj[u]){
if(!extras[v]) continue;
int bit = anchorMap[v];
value |= (1 << bit);
}
int pos = lower_bound(nums.begin(),nums.end(),value) - nums.begin();
normalMap[u] = pos;
//cout << u << " " << pos << "\n";
}
vector<ii> finalEdges;
for(int i = 0;i < m;i++){
int u = C[i];
int v = D[i];
if(extras[u] || extras[v]) continue;
finalEdges.push_back(ii(normalMap[u],normalMap[v]));
}
//cout << "\n";
//for(ii k : finalEdges) cout << k.first << " " << k.second << "\n";
InitMap(on, finalEdges.size());
for(ii k : finalEdges) MakeMap(k.first,k.second);
}
