#include<bits/stdc++.h>
#define pb push_back
#define fr first
#define sc second
using namespace std;
#include "Alicelib.h"
static int n,m;
static int k=10,s;
static vector<pair<int,int>>v;
void Alice(int N,int M,int A[],int B[]){
n=N;
m=M;
s=n+k+2;
for(int i=0;i<m;i++){
v.pb({A[i],B[i]});
}
for(int i=0;i<n;i++){
v.pb({i,s-2});
for(int j=0;j<k;j++){
if(((i)>>j)&1){
v.pb({i,n+j});
}
}
}
for(int i=0;i<k;i++){
v.pb({n+i,s-1});
v.pb({n+i,s-2});
if(i){
v.pb({n+i-1,n+i});
}
}
InitG(s,v.size());
for(int i=0;i<v.size();i++){
MakeG(i,v[i].fr,v[i].sc);
}
}
#include<bits/stdc++.h>
#define pb push_back
#define fr first
#define sc second
using namespace std;
#include "Boblib.h"
static int n,m;
static int k=10;
static int arr[1012];
static vector<int>bit,v,komsu[1012];
static int boss,cool;
static vector<pair<int,int>>ans;
void Bob(int V,int U,int C[],int D[]){
n=V;m=U;
for(int i=0;i<m;i++){
komsu[C[i]].pb(D[i]);
komsu[D[i]].pb(C[i]);
}
for(int i=0;i<n;i++){
if(komsu[i].size()==n-2){
boss=i;
arr[i]=-3;
}
else arr[i]=-1;
}
for(int x:komsu[boss]){
arr[x]=0;
}
for(int i=0;i<n;i++){
if(arr[i]==-1){
cool=i;
}
}
for(int x:komsu[cool]){
arr[x]=-2;
}
for(int i=0;i<n;i++){
if(arr[i]==0)v.pb(i);
if(arr[i]==-2)bit.pb(i);
}
vector<int>temp;
int pos;
for(int x:bit){
int cnt=0;
for(int y:komsu[x]){
if(arr[y]==-2)cnt++;
}
if(cnt==1){
pos=x;
break;
}
}
while(true){
int nex=-1;
temp.pb(pos);
arr[pos]=1;
for(int x:komsu[pos]){
if(arr[x]==-2){
nex=x;
}
}
if(nex==-1)break;
pos=nex;
}
swap(temp,bit);
for(int x:temp){
arr[x]=-2;
}
if(komsu[bit[0]].size()<komsu[bit.back()].size()){
reverse(bit.begin(),bit.end());
}
for(int i=0;i<k;i++){
for(int x:komsu[bit[i]]){
if(arr[x]<0)continue;
arr[x]+=(1<<i);
}
}
for(int x:v){
for(int y:komsu[x]){
if(arr[y]<0)continue;
if(y<x)continue;
ans.pb({arr[x],arr[y]});
}
}
InitMap(v.size(),ans.size());
for(auto x:ans){
MakeMap(x.fr,x.sc);
}
}
