#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
static vpi eds;
static int deg[1505];
void Alice( int N, int M, int A[], int B[]){
eds.clear();
for(int i = 0; i < 1505; i++){
deg[i] = 0;
}
for(int i = 0; i < M; i++){
eds.pb(mp(A[i], B[i]));
}
for(int i = 0; i < N; i++){
for(int j = 0; j < 10; j++){
if((i>>j)&1){
eds.pb(mp(i, N+j));
}
}
}
vpi tree_eds = vpi{mp(0, 1), mp(0, 2), mp(2, 3), mp(0, 4), mp(4, 5), mp(5, 6), mp(6, 7), mp(7, 8), mp(8, 9)};
for(auto u: tree_eds){
eds.pb(mp(N+u.f, N+u.s));
}
for(int j = 0; j < 10; j++){
eds.pb(mp(N+j, N+11));
}
for(auto u: eds){
deg[u.f]++;
deg[u.s]++;
}
for(int i = 0; i < N+10; i++){
if((deg[i]&1)^((i >= N)&(i <= N+9))){
eds.pb(mp(i, N+10));
}
}
InitG(N+12, sz(eds));
// cout << "nodes: " << N+12 << "\n";
// cout << "Actual graph: " << "\n";
for(int i = 0; i < sz(eds); i++){
MakeG(i, eds[i].f, eds[i].s);
// cout << eds[i].f << " " << eds[i].s << "\n";
}
}
#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
static bool adj[1505][1505];
static int deg[1505];
static int original_ind[1505];
static bool pres[1505];
static vi small_adj[10];
static vi checkSmall(vpi small_eds){
// cout << "checkSmall(";
// for(auto u: small_eds){
// cout << u.f << " " << u.s << "\n";
// }
// cout << ")" << "\n";
if(sz(small_eds) != 9) return vi{};
for(auto u: small_eds){
assert(0 <= u.f && u.s <= 9);
}
int cen = -1;
for(int i = 0; i < 10; i++){
small_adj[i].clear();
}
for(auto u: small_eds){
small_adj[u.f].pb(u.s);
small_adj[u.s].pb(u.f);
}
for(int i = 0; i < 10; i++){
if(sz(small_adj[i]) == 3){
if(cen == -1){
cen = i;
}
else{
cen = -2;
}
}
}
if(cen < 0) return vi{};
//cout << "cen: " << cen << "\n";
vector<pair<int, vi>> branches;
bool works = 1;
for(auto node: small_adj[cen]){
vi branch;
int last_node = cen;
while(true){
if(node == cen){ //cycle
works = 0;
break;
}
branch.pb(node);
if(sz(small_adj[node]) == 1) break;
if(sz(small_adj[node]) != 2){
works = 0;
break;
}
if(small_adj[node][0] == last_node){
last_node = node;
node = small_adj[node][1];
}
else{
last_node = node;
node = small_adj[node][0];
}
}
branches.pb(mp(sz(branch), branch));
if(!works) break;
}
if(!works) return vi{};
sort(all(branches));
if(sz(branches) != 3 || branches[0].f != 1 || branches[1].f != 2 || branches[2].f != 6) return vi{};
vi res(10, 0);
res[0] = cen;
int cur = 0;
for(auto &u: branches){
for(auto &x: u.s){
res[++cur] = x;
}
}
// cout << "res: ";
// for(auto u: res){
// cout << u << " ";
// }
// cout << "\n";
return res;
}
void Bob( int V, int U, int C[], int D[] ){
for(int i = 0; i < 1505; i++){
for(int j = 0; j < 1505; j++){
adj[i][j] = 0;
}
}
for(int i = 0; i < 1505; i++){
deg[i] = 0;
original_ind[i] = 0;
}
int N = V-12;
//cout << "encrypted graph: " << "\n";
for(int i = 0; i < U; i++){
adj[C[i]][D[i]] = 1;
adj[D[i]][C[i]] = 1;
deg[C[i]]++; deg[D[i]]++;
//cout << C[i] << " " << D[i] << "\n";
}
vector<pair<int, vi>> bin_cands;
for(int spec_node = 0; spec_node < V; spec_node++){
vi dif_nodes;
for(int i = 0; i < V; i++){
if(spec_node == i) continue;
if(adj[i][spec_node]){
deg[i]--;
}
}
for(int i = 0; i < V; i++){
if(spec_node == i) continue;
bool is_dif = 0;
if(adj[i][spec_node]){
is_dif^=1;
}
if(deg[i]&1){
is_dif^=1;
}
if(is_dif){
dif_nodes.pb(i);
}
}
// if(spec_node == 7){
// cout << "dif_nodes: ";
// for(auto u: dif_nodes){
// cout << u << " ";
// }
// cout << "\n";
// }
for(int i = 0; i < V; i++){
if(spec_node == i) continue;
if(adj[i][spec_node]){
deg[i]++;
}
}
if(sz(dif_nodes) == 10){
bin_cands.pb(mp(spec_node, dif_nodes));
}
}
vpi ans;
for(auto x: bin_cands){
//cout << "spec node: " << x.f << "\n";
vi bins = x.s;
// cout << "bins: " << "\n";
// for(auto u: bins){
// cout << u << " ";
// }
// cout << "\n";
vpi small_eds;
for(int i = 0; i < sz(bins); i++){
for(int j = i+1; j < sz(bins); j++){
if(adj[bins[i]][bins[j]]){
small_eds.pb(mp(i, j));
}
}
}
vi res = checkSmall(small_eds); //bins[res[i]] is original node N+i
if(sz(res) == 0) continue;
int add_node = -1;
for(int i = 0; i < V; i++){
if(i == x.f) continue;
bool is_add_node = 1;
for(int j = 0; j < 10; j++){
if(bins[j] == i){
is_add_node = 0;
break;
}
if(!adj[i][bins[j]]){
is_add_node = 0;
break;
}
}
if(deg[i] != 10){
is_add_node = 0;
}
if(is_add_node){
if(add_node == -1){
add_node = i;
}
else{
add_node = -2;
}
}
}
if(add_node < 0){
continue;
}
for(int i = 0; i < V; i++){
original_ind[i] = 0;
}
for(int i = 0; i < 10; i++){
for(int j = 0; j < V; j++){
if(adj[bins[res[i]]][j]){
original_ind[j]+=(1<<i);
}
}
}
original_ind[x.f] = -1;
original_ind[add_node] = -1;
for(auto u: bins){
original_ind[u] = -1;
}
for(int i = 0; i < N; i++){
pres[i] = 0;
}
for(int i = 0; i < V; i++){
if(original_ind[i] == -1) continue;
if(0 <= original_ind[i] && original_ind[i] < N){
pres[original_ind[i]] = 1;
}
}
bool works = 1;
for(int i = 0; i < N; i++){
if(!pres[i]){
works = 0;
break;
}
}
if(!works) continue;
for(int i = 0; i < V; i++){
for(int j = i+1; j < V; j++){
if(original_ind[i] >= 0 && original_ind[j] >= 0){
if(adj[i][j]){
ans.pb(mp(original_ind[i], original_ind[j]));
}
}
}
}
break;
}
InitMap(V-12, sz(ans));
for(auto u: ans){
MakeMap(u.f, u.s);
}
}
