#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <utility>
#include <iostream>
const int K = 10;
void Alice( int N, int M, int A[], int B[] ){
if(N == 1) {
InitG(N, M);
return;
}
if(N == 2) {
InitG(N, M);
if(M) MakeG(0, 0, 1);
return;
}
std::vector<std::pair<int, int> > edges;
for(int i = 0; i < M; i++) {
edges.emplace_back(A[i], B[i]); // original graph
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < K; j++) {
if(!((i + 1) >> j & 1)) continue; // make graph 1-indexed, so connect to corresponding nodes
edges.emplace_back(i, N + j); // links between bit vertices and origianl vertices
}
}
for(int j = 0; j < K - 1; j++) edges.emplace_back(N + j, N + j + 1); // links between bit vertices
for(int i = 0; i < N; i++) {
edges.emplace_back(i, N + K); // N + 10 is the special vertex
}
edges.emplace_back(N + K, N + K + 1); // N + 11 is the one-degree vertex
int curr_idx = 0;
InitG(N + K + 2, edges.size());
// for(auto p: edges) std::cerr << p.first << ' ' << p.second << std::endl;
for(auto p: edges) MakeG(curr_idx++, p.first, p.second);
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
const int K = 10;
void Bob(int N, int M, int A[], int B[]) {
if(N == 1) {
InitMap(N, M);
return;
}
if(N == 2) {
InitMap(N, M);
for(int i = 0; i < M; i++) MakeMap(A[i], B[i]);
return;
}
std::vector<int> g[N];
for(int i = 0; i < M; i++) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
// std::cerr << A[i] << ' ' << B[i] << ' ' << std::endl;
}
//find special vertex
std::vector<int> deg1;
for(int i = 0; i < N; i++) if(g[i].size() == 1) deg1.push_back(i);
assert(deg1.size() <= 2);
int very_special_vertex = deg1[0]; // vertex of degree 1 that points to the special vertex
int special_vertex = g[deg1[0]][0];
if(deg1.size() == 2) {
if(g[special_vertex].size() != N - K - 1) {
very_special_vertex = deg1[1];
special_vertex = g[deg1[1]][0];
}
}
// std::cerr << "specials " << very_special_vertex << ' ' << special_vertex << std::endl;
// std::cerr << "bit_vertices " << std::endl;
//find bit vertices
std::vector<int> bit_vertices;
std::vector<bool> is_bit_vertex(N);
for(int i = 0; i < N; i++) if(i != special_vertex) {
if(std::find(g[i].begin(), g[i].end(), special_vertex) == g[i].end()) {
bit_vertices.push_back(i);
is_bit_vertex[i] = true;
}
}
assert(bit_vertices.size() == K);
int mx_bit_vertex = *min_element(bit_vertices.begin(), bit_vertices.end(), [&] (int i, int j) { return g[i].size() < g[j].size(); });
std::vector<int> vals(N);
for(int ord = K - 1, curr = mx_bit_vertex; ord >= 0; ord--) {
// std::cerr << curr << ' ' << ord << std::endl;
for(int v: g[curr]) {
assert(v != very_special_vertex && v != special_vertex);
if(is_bit_vertex[v]) continue;
vals[v] |= 1 << ord;
}
for(int v: g[curr]) {
if(is_bit_vertex[v]) {
g[v].erase(std::find(g[v].begin(), g[v].end(), curr));
curr = v;
break;
}
}
}
auto in_org_graph = [&] (int v) -> bool { return v != very_special_vertex && v != special_vertex && !is_bit_vertex[v]; };
std::vector<std::pair<int,int> > ans;
for(int i = 0; i < M; i++) {
if(in_org_graph(A[i]) && in_org_graph(B[i])) ans.emplace_back(vals[A[i]] - 1, vals[B[i]] - 1);
}
InitMap(N - K - 2, ans.size());
// for(auto p: ans) std::cerr << p.first << ' ' << p.second << std::endl;
for(auto p: ans) MakeMap(p.first, p.second);
}
