#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
std::vector<std::pair<int,int>> Alice(){
const int num_cmps = 25;
int n = 5000;
const int mega_root = 3541;
// add your code here
int cmp_size = (n - 1) / num_cmps;
n = cmp_size * num_cmps + 1;
mt19937_64 rand(53);
ll mask = rand() % (1LL << num_cmps);
ll x = setN(n) ^ mask;
vector<pii> out;
vector<int> all_nodes(n);
iota(all_nodes.begin(), all_nodes.end(), 1);
all_nodes.erase(all_nodes.begin() + mega_root - 1);
shuffle(all_nodes.begin(), all_nodes.end(), rand);
for (int cmp = 0; cmp < num_cmps; cmp++) {
out.emplace_back(all_nodes[cmp * cmp_size], mega_root);
if ((1LL << cmp) & x) {
for (int i = 1; i < cmp_size; i++)
out.emplace_back(all_nodes[cmp * cmp_size + i], all_nodes[cmp * cmp_size + i - 1]);
} else {
for (int i = 1; i < cmp_size; i++)
out.emplace_back(all_nodes[cmp * cmp_size + i], all_nodes[cmp * cmp_size]);
}
}
return out;
}
#include <bits/stdc++.h>
#include "Bob.h"
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int num_cmps = 25;
int n = 5000;
const int mega_root = 3541;
// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
long long Bob(std::vector<std::pair<int,int>> V){
// add your code here
int cmp_size = (n - 1) / num_cmps;
n = cmp_size * num_cmps + 1;
mt19937_64 rand(53);
ll mask = rand() % (1LL << num_cmps);
ll x = 0;
vector<pii> out;
vector<int> all_nodes(n);
iota(all_nodes.begin(), all_nodes.end(), 1);
all_nodes.erase(all_nodes.begin() + mega_root - 1);
shuffle(all_nodes.begin(), all_nodes.end(), rand);
vector<int> what_cmp(n);
vector<int> deg(n);
for (auto [x, y] : V) {
deg[x]++;
deg[y]++;
}
for (int cmp = 0; cmp < num_cmps; cmp++)
{
if (deg[all_nodes[cmp * num_cmps]] <= 1)
x += (1LL << cmp);
}
x ^= mask;
return x; // change this into your code
}
