#include "Alicelib.h"
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;
using pii=pair<int, int>;
void InitG(int V, int U);
void MakeG(int pos, int C, int D);
namespace encode_sub12
{
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]});
int cnt=N;
for (int i=0; i<N; i++)
{
for (int j=1; j<=i+2; j++)
{
E.push_back({i, cnt++});
}
}
InitG(1500, E.size());
for (int i=0; i<E.size(); i++)
{
MakeG(i, E[i].first, E[i].second);
//cerr<<E[i].first<<' '<<E[i].second<<endl;
}
}
}
namespace encode
{
void Alice(int N, int M, int A[], int B[])
{
assert(0);
}
}
void Alice(int N, int M, int A[], int B[])
{
if (N<=40) encode_sub12::Alice(N, M, A, B);
else encode::Alice(N, M, A, B);
}
#include "Boblib.h"
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;
using pii=pair<int, int>;
void InitMap(int N, int M);
void MakeMap(int A, int B);
namespace decode_sub12
{
void Bob(int V, int U, int C[], int D[])
{
int deg[V]={0}, id[V];
for (int i=0; i<V; i++) id[i]=-2;
for (int i=0; i<U; i++)
{
deg[C[i]]++;
deg[D[i]]++;
}
for (int i=0; i<U; i++)
{
//cerr<<C[i]<<' '<<D[i]<<endl;
if (deg[C[i]]==1)
{
assert(deg[D[i]]>1);
id[D[i]]++;
}
if (deg[D[i]]==1)
{
assert(deg[C[i]]>1);
id[C[i]]++;
}
}
//for (int i=0; i<V; i++) cerr<<deg[i]<<' '; cerr<<endl;
//for (int i=0; i<V; i++) cerr<<id[i]<<' '; cerr<<endl;
int mx=0; vector<pii> E;
for (int i=0; i<U; i++)
{
if (deg[C[i]]==1) assert(id[C[i]]==-2);
else if (deg[D[i]]==1) assert(id[D[i]]==-2);
else E.push_back({id[C[i]], id[D[i]]});
mx=max(mx, id[C[i]]);
mx=max(mx, id[D[i]]);
}
InitMap(mx+1, E.size());
for (auto [u, v]:E) MakeMap(u, v);
}
}
namespace decode
{
void Bob(int V, int U, int C[], int D[])
{
assert(0);
}
}
void Bob(int V, int U, int C[], int D[])
{
if (V==1500) decode_sub12::Bob(V, U, C, D);
else decode::Bob(V, U, C, D);
}
