#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define X first
#define Y second
#define SZ(x) int((x).size())
const int MAXN = 1510;
const int LOG = 10;
void Alice(int N, int M, int A[], int B[]){
vector<pii> E;
for(int i = 0 ; i < M ; i++){
E.push_back({A[i] , B[i]});
}
for(int i = N ; i <= N + 100 ; i++){
for(int j = 0 ; j < i ; j++){
E.push_back({j , i});
}
}
for(int i = N + 101 ; i <= N + 200 ; i++){
for(int j = N ; j <= N + 100 ; j++){
if(i % 2 == j % 2){
E.push_back({j , i});
}
}
}
for(int i = 0 ; i < LOG ; i++){
for(int j = 0 ; j < N ; j++){
if(j & (1 << i)){
E.push_back({j , N + 201 + i});
}
}
for(int j = N ; j < N + i ; j++){
E.push_back({j , N + 201 + i});
}
}
InitG(N + 201 + LOG , SZ(E));
for(int i = 0 ; i < SZ(E) ; i++){
MakeG(i , E[i].X , E[i].Y);
}
}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define X first
#define Y second
#define SZ(x) int((x).size())
const int MAXN = 1510;
const int LOG = 10;
int deg[MAXN] , deg2[MAXN] , ind[MAXN] , type[MAXN];
void Bob(int N, int M, int A[], int B[]){
for(int i = 0 ; i < M ; i++){
deg[A[i]]++;
deg[B[i]]++;
}
for(int i = 0 ; i < N ; i++){
if(deg[i] >= N - LOG - 50 - 1){
type[i] = 1;
}
}
for(int i = 0 ; i < M ; i++){
if(type[A[i]] == 1) deg2[B[i]]++;
if(type[B[i]] == 1) deg2[A[i]]++;
}
int n = 0 , m = 0;
for(int i = 0 ; i < N ; i++){
if(type[i] == 1) continue;
if(deg2[i] >= 100){
type[i] = 0;
n++;
}
else if(deg2[i] >= 50){
type[i] = 2;
}
else{
type[i] = 3;
}
}
vector<pii> E;
for(int i = 0 ; i < M ; i++){
if(type[A[i]] > type[B[i]]) swap(A[i] , B[i]);
if(type[A[i]] == 0 && type[B[i]] == 3){
ind[A[i]] |= (1 << deg2[B[i]]);
}
if(type[B[i]] == 0){
E.push_back({A[i] , B[i]});
}
}
m = SZ(E);
InitMap(n , m);
for(pii i : E){
MakeMap(ind[i.X] , ind[i.Y]);
}
}
