#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <vector>
#define X first
#define Y second
#define PB push_back
using namespace std;
const int N = 1055;
const int M = N * N;
typedef pair < int, int > pii;
int nnn, imaa[M], uk = 0, encode[N][N], koliko = 0;
int decodeA[M], decodeB[M];
vector < pii > bezveze;
int glp[N][N];
void jako_glupo(){
srand(123);
for(int i = 0;i < 12;i++)
for(int j = i + 1;j < 12;j++){
glp[i][j] = glp[j][i] = rand() % 2;
//if(glp[i][j]) printf("%d --- %d\n", i, j);
}
}
void precompute(){
for(int i = 0;i < nnn;i++){
for(int j = i + 1;j < nnn;j++){
encode[i][j] = koliko;
encode[j][i] = koliko;
decodeA[koliko] = i;
decodeB[koliko] = j;
koliko++;
}
}
}
void zakompliciraj(){
srand(69);
vector < int > v;
for(int i = 0;i < 5 * M;i++){
v.PB(rand() % koliko); v.PB(rand() % koliko);
}
//printf("%d\n", v[0]);
for(int i = 0;i < 10 * M;i += 2){
//printf("mijenjam %d i %d\n", v[i], v[i + 1]);
swap(imaa[v[i]], imaa[v[i + 1]]);
}
}
void Alice( int nn, int mm, int A[], int B[] ){
nnn = nn; precompute(); jako_glupo();
for(int i = 0;i < mm;i++)
imaa[encode[A[i]][B[i]]] = 1;
zakompliciraj();
for(int i = 0;i < nn * nn;i++){
if(imaa[i]) bezveze.PB({decodeA[i], decodeB[i]});
}
for(int i = nn;i < nn + 12;i++){
for(int j = 0;j < nn;j++){
if((j & (1 << (i - nn))))
bezveze.PB({i, j});
}
for(int j = 0;j < i - nn;j++){
if(glp[i - nn][j])
bezveze.PB({i, j + nn});
}
}
InitG(nn + 12, (int)bezveze.size());
for(int i = 0;i < (int)bezveze.size();i++){
//printf("%d --- %d\n", bezveze[i].X, bezveze[i].Y);
MakeG(i, bezveze[i].X, bezveze[i].Y);
}
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef pair < int, int > pii;
const int N = 1055;
const int M = N * N;
int n2, m2, n, m, ima[M], spj[N][N], glp2[N][N];
int trb[N], poseban[N], prav[N];
int cur[N], tko[N], gotov = 0, poten[N], deg[N];
int encode2[N][N], koliko2;
int decodeA2[M], decodeB2[M];
vector < int > kand[N];
void jako_glupo2(){
srand(123);
for(int i = 0;i < 12;i++)
for(int j = i + 1;j < 12;j++){
glp2[i][j] = glp2[j][i] = rand() % 2;
//if(glp2[i][j]) printf("%d --- %d\n", i, j);
}
}
void precompute2(){
for(int i = 0;i < n;i++){
for(int j = i + 1;j < n;j++){
encode2[i][j] = koliko2;
encode2[j][i] = koliko2;
decodeA2[koliko2] = i;
decodeB2[koliko2] = j;
koliko2++;
}
}
}
void zakompliciraj_obrnuto(){
srand(69);
vector < int > v;
for(int i = 0;i < 5 * M;i++){
v.PB(rand() % koliko2); v.PB(rand() % koliko2);
}
//printf("%d\n", v[0]);
reverse(v.begin(), v.end());
for(int i = 0;i < 10 * M;i += 2){
//printf("mijenjam %d i %d\n", v[i], v[i + 1]);
swap(ima[v[i]], ima[v[i + 1]]);
}
}
void probaj(int i){
if(i == 12){
gotov = 1; return;
}
for(int x : kand[i]){
if(poseban[x]) continue;
int mogu = 1;
for(int j = 0;j < i;j++)
if(spj[x][tko[j]] != glp2[i][j])
mogu = 0;
if(!mogu) continue;
tko[i] = x; poseban[x] = 1; poten[x] = i;
probaj(i + 1);
if(gotov) return;
poseban[x] = 0;
}
}
void Bob( int nn, int mm, int C[], int D[] ){
n2 = nn; n = nn - 12; precompute2(); jako_glupo2();
for(int i = 0;i < 12;i++){
for(int j = 0;j < n;j++)
trb[i] += !!(j & (1 << i));
for(int j = 0;j < 12;j++)
trb[i] += glp2[i][j];
}
for(int i = 0;i < mm;i++){
deg[C[i]]++, deg[D[i]]++;
//printf("%d --- %d\n", C[i], D[i]);
spj[C[i]][D[i]] = 1; spj[D[i]][C[i]] = 1;
}
for(int i = 0;i < n2;i++){
for(int j = 0;j < 12;j++){
if(deg[i] == trb[j])
kand[j].PB(i);// printf("%d kandidat za %d\n", i, j);
}
}
probaj(0); //printf("gotov = %d\n", gotov);
for(int i = 0;i < n2;i++){
if(!poseban[i]) continue;
//printf("POSEBAN : %d je %d\n", i, poten[i]);
for(int j = 0;j < n2;j++){
if(spj[i][j])
prav[j] += (1 << poten[i]);
}
}
for(int j = 0;j < n2;j++){
if(poseban[j]) continue;
//printf("%d ---> %d\n", j, prav[j]);
}
int uk = 0;
for(int i = 0;i < mm;i++){
if(poseban[C[i]]) continue;
if(poseban[D[i]]) continue;
ima[encode2[prav[C[i]]][prav[D[i]]]] = 1;
//printf("%d --- %d tj. %d --- %d\n",C[i], D[i],prav[C[i]], prav[D[i]]);
uk++;
}
zakompliciraj_obrnuto();
InitMap(n, uk);
for(int i = 0;i < M;i++){
if(ima[i]) {
//printf("spajam %d i %d\n", decodeA2[i], decodeB2[i]);
MakeMap(decodeA2[i], decodeB2[i]);
}
}
}
