/*input
*/
#include <bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
static unordered_map<int, int> sk = {
{511, 1000},
{767, 1001},
{895, 1002},
{959, 1003},
{991, 1004},
{1007, 1005},
{1015, 1006},
{1019, 1008},
{1021, 1009},
{1022, 1010},
};
void Alice( int N, int M, int A[], int B[] ) {
for (int i = 0; i < N; ++i)
{
if (__builtin_popcount(i) != 9)
sk[i] = i;
}
vpi edges;
for (int i = 0; i < M; ++i) {
edges.emplace_back(A[i], B[i]);
}
for (int i = 0; i < 9; ++i)
{
edges.emplace_back(N + i, N + i + 1);
}
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < 10; ++j)
{
if ((sk[i] >> j) & 1)
edges.emplace_back(i, N + j);
}
edges.emplace_back(N + 10, i);
}
for (int i = 0; i < N + 10; ++i)
edges.emplace_back(N + 11, i);
InitG( N + 12, (int)edges.size());
for (int i = 0; i < (int)edges.size(); ++i)
{
// printf("%d %d\n", edges[i].x, edges[i].y);
MakeG(i, edges[i].x, edges[i].y);
}
}
/*input
*/
#include <bits/stdc++.h>
#include "Boblib.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
static unordered_map<int, int> sk = {
{1000, 511},
{1001, 767},
{1002, 895},
{1003, 959},
{1004, 991},
{1005, 1007},
{1006, 1015},
{1008, 1019},
{1009, 1021},
{1010, 1022},
};
void Bob( int V, int U, int C[], int D[] ) {
// printf("IM IN BOB\n");
int N = V - 12;
vi kas(V, 0);
vii edges(V);
for (int i = 0; i < U; ++i)
{
edges[C[i]].emplace_back(D[i]);
edges[D[i]].emplace_back(C[i]);
}
int n11 = -1;
for (int i = 0; i < V; ++i)
{
if ((int)edges[i].size() == N + 10) {
kas[i] = N + 11;
n11 = i;
break;
}
}
int n10 = 0;
{
vb buvo(V, false);
buvo[n11] = true;
for (auto u : edges[n11])
buvo[u] = true;
for (int i = 0; i < V; ++i)
{
if (!buvo[i]) {
n10 = i;
kas[i] = N + 10;
}
}
}
vi pirmiN;
// vi bitai;
vi bit(10);
vb bitas(V, true);
{
// vb buvo(V, false);
bitas[n11] = false;
bitas[n10] = false;
for (auto u : edges[n10]) {
pirmiN.emplace_back(u);
bitas[u] = false;
}
vi sonai;
for (int i = 0; i < V; ++i) {
if (bitas[i]) {
int cnt = 0;
for (auto u : edges[i]) {
if (bitas[u])
cnt++;
}
if (cnt == 1)
sonai.emplace_back(i);
}
}
assert(sonai.size() == 2);
int n0;
if (edges[sonai[0]].size() > edges[sonai[1]].size())
n0 = sonai[0];
else
n0 = sonai[1];
kas[n0] = N + 0;
bit[0] = n0;
int curr = n0;
bool ch = true;
while (ch) {
ch = false;
for (auto u : edges[curr]) {
if (bitas[u]) {
bitas[curr] = false;
kas[u] = kas[curr] + 1;
bit[kas[u] - N] = u;
curr = u;
ch = true;
break;
}
}
}
}
{
for (int i = 0; i < 10; ++i)
{
for (auto u : edges[bit[i]]) {
if (kas[u] >= N) continue;
kas[u] |= (1 << i);
}
}
}
// print(kas);
// printf("ATS\n");
vpi ats;
for (int i = 0; i < U; ++i)
{
if (sk.count(kas[i])) kas[i] = sk[kas[i]];
if (kas[C[i]] < N and kas[D[i]] < N) {
// printf("%d %d\n", kas[C[i]], kas[D[i]]);
ats.emplace_back(kas[C[i]], kas[D[i]]);
}
}
InitMap( N, (int)ats.size());
for (auto u : ats)
MakeMap(u.x, u.y);
}
