#include "Alice.h"
#include <random>
#include <vector>
std::vector<std::pair<int, int>> Alice() {
const int seed = 69;
const int bits = 60;
const int n = 5000;
long long x = setN(n);
std::mt19937 rng(seed);
std::uniform_int_distribution<int> dist(0, 1);
std::vector<std::pair<int, int>> adj;
adj.push_back({1, 2});
for (int i = 0; i < n - 2; ++i) {
int sum = 0;
for (int j = 0; j < bits; ++j) {
sum ^= !!(x & (1LL << j)) * dist(rng);
}
sum ^= dist(rng);
if (sum & 1) {
adj.push_back({1, i + 3});
} else {
adj.push_back({2, i + 3});
}
}
return adj;
}
#include "Bob.h"
#include <cassert>
#include <random>
#include <vector>
long long Bob(std::vector<std::pair<int, int>> V) {
const int seed = 69;
const int bits = 60;
const int n = 5000;
std::mt19937 rng(seed);
std::uniform_int_distribution<int> dist(0, 1);
std::vector<long long> a(n - 2);
for (int i = 0; i < n - 2; ++i) {
for (int j = 0; j < bits + 1; ++j) {
a[i] += (1LL << j) * dist(rng);
}
}
std::vector<bool> good(n - 2);
for (auto &[u, v] : V) {
if (u == 1 and v == 2) {
continue;
}
a[v - 3] ^= (1LL << bits) * (u % 2);
good[v - 3] = true;
}
for (int i = 0; i < n - 2; ++i) {
if (!good[i]) {
a[i] = 0;
}
}
long long x = 0;
// i ==> eq number, j ==> var number
auto solve = [&](auto &&self, int i, int j) {
if (i >= a.size()) {
return;
}
if (!(a[i] & (1LL << j))) {
for (int k = i + 1; k < a.size(); ++k) {
if (a[k] & (1LL << j)) {
std::swap(a[i], a[k]);
break;
}
}
}
if (!(a[i] & (1LL << j))) {
return;
}
for (int k = i + 1; k < a.size(); ++k) {
if (a[k] & (1LL << j)) {
a[k] ^= a[i];
}
}
if (j == bits - 1) {
x += (1LL << j) * !!(a[i] & (1LL << bits));
return;
}
self(self, i + 1, j + 1);
int ans = !!(a[i] & (1LL << bits));
for (int k = j + 1; k < bits; ++k) {
if (a[i] & (1LL << k)) {
ans -= !!(x & (1LL << k));
}
}
ans = (ans % 2 + 2) % 2;
x += (1LL << j) * ans;
};
solve(solve, 0, 0);
return x;
}
