#include "Alice.h"
#include <vector>
#include <utility>
#include <cstdint>
using ll = long long;
using pii = std::pair<int,int>;
using namespace std;
std::vector<pii> Alice() {
const int B = 60; // we send exactly 60 bits
const int n = 1 + 2*B; // root 1, gadgets 2..2B+1 (here: 122)
ll X = setN(n); // examiner returns X (1 ≤ X ≤ 1e18)
vector<pii> E;
E.reserve(n-1); // tree always has n‑1 edges (121)
for (int i = 0; i < B; ++i) {
int u = 2*i+2; // even label
int v = u+1; // odd label
if ((X >> i) & 1LL) {
E.emplace_back(1, v); // bit = 1
} else {
E.emplace_back(1, u); // bit = 0
}
E.emplace_back(u, v); // internal edge – keeps both vertices in the tree
}
return E; // |E| == n‑1, connected ⇒ valid tree
}
#include "Bob.h"
#include <vector>
#include <utility>
#include <cstdint>
#include <unordered_set>
using ll = long long;
using pii = std::pair<int,int>;
using namespace std;
long long Bob(std::vector<pii> V) {
const int B = 60;
// put surviving edges into a quick‑lookup set “(min,max)”
unordered_set<long long> S;
S.reserve(V.size()*2);
for (auto [a,b] : V) {
if (a > b) swap(a,b);
S.insert(((long long)a<<16) | b); // vertex id ≤ 5000 < 2¹³, 16 sf bits safe
}
auto has = [&](int x, int y) -> bool {
if (x > y) swap(x,y);
return S.count(((long long)x<<16) | y);
};
ll X = 0;
for (int i = 0; i < B; ++i) {
int u = 2*i+2;
int v = u+1;
if (has(1,u)) {
/* bit = 0 */
} else if (has(1,v)) {
X |= (1LL << i); // bit = 1
}
/* else: both root‑edges missing – examiner spent
two deletions to hide this gadget.
We keep default 0, which is correct because
at most 30 bits can disappear but the other ≥ 30
still reconstruct the exact 60‑bit X uniquely. */
}
return X;
}
