// meetings.cpp
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
// ---------- Utilities ----------
static inline long long keyEdge(int u, int v) {
if (u > v) swap(u, v);
return ( (long long)u << 21 ) ^ (long long)v; // N <= 2000 fits well
}
struct Reconstructor {
int N;
vector<vector<int>> adj; // for optional internal checks (not needed by grader)
unordered_set<long long> edge_set; // to avoid duplicate Bridge calls
Reconstructor(int n): N(n) {
adj.assign(N, {});
edge_set.reserve(2*N);
}
// Safely add one real edge (u,v) once.
void add_edge(int u, int v) {
if (u > v) swap(u, v);
long long k = keyEdge(u, v);
if (edge_set.insert(k).second) {
// Record edge for sanity (optional)
adj[u].push_back(v);
adj[v].push_back(u);
}
}
// Projection of x onto path (A,B). Avoids duplicate-node queries.
int project(int A, int B, int x) {
if (x == A) return A;
if (x == B) return B;
return Query(A, B, x);
}
// Find diameter endpoints of set S (one pass, ~|S|-2 queries).
pair<int,int> find_diameter(const vector<int>& S) {
int a = S[0];
int b = S[1 % (int)S.size()];
for (int i = 0; i < (int)S.size(); ++i) {
int x = S[i];
if (x == a || x == b) continue;
int p = project(a, b, x);
if (p == a) a = x;
else if (p == b) b = x;
// else x is inside current path; ignore
}
return {a, b};
}
// Comparator to order nodes u,v that we know lie on path A-B:
// u comes before v from A towards B iff Query(A,u,v) == u.
struct PathLess {
int A;
PathLess(int A): A(A) {}
bool operator()(int u, int v) const {
if (u == v) return false;
if (u == A) return true;
if (v == A) return false;
int m = Query(A, u, v);
return m == u; // u is between A and v => u is closer to A than v
}
};
void build_on_set(const vector<int>& S) {
if ((int)S.size() <= 1) return;
// 1) Find diameter endpoints (A,B)
auto pr = find_diameter(S);
int A = pr.first, B = pr.second;
// 2) Project everything onto A-B, split into on-path and buckets
vector<int> onpath;
onpath.reserve(S.size());
unordered_map<int, vector<int>> bucket; // projection point -> nodes hanging there
bucket.reserve(S.size()*2);
for (int x : S) {
int p;
if (x == A || x == B) {
p = x; // avoid duplicate-node query
} else {
p = project(A, B, x);
}
if (p == x) {
onpath.push_back(x);
} else {
bucket[p].push_back(x);
}
}
// 3) Sort path nodes from A to B using median comparator
// (A will naturally be first due to the comparator handling)
sort(onpath.begin(), onpath.end(), PathLess(A));
// 4) Add edges along this path (consecutive nodes are adjacent in the real tree)
for (int i = 0; i + 1 < (int)onpath.size(); ++i) {
add_edge(onpath[i], onpath[i+1]);
}
// 5) Recurse on each hanging component {t} ∪ bucket[t]
for (int t : onpath) {
auto it = bucket.find(t);
if (it == bucket.end() || it->second.empty()) continue;
vector<int> sub;
sub.reserve(it->second.size() + 1);
sub.push_back(t);
for (int v : it->second) sub.push_back(v);
build_on_set(sub);
}
}
void run() {
// Start with the full set of nodes
vector<int> all(N);
iota(all.begin(), all.end(), 0);
build_on_set(all);
// At this point we should have exactly N-1 distinct edges.
// Report them via Bridge(u,v).
// (The grader requires exactly N-1 calls, all correct and unique.)
// For determinism, iterate through adjacency or through the set.
// We'll iterate through the set we maintained.
vector<pair<int,int>> edges;
edges.reserve(N-1);
edges.clear();
for (long long k : edge_set) {
int u = (int)(k >> 21);
int v = (int)(k & ((1<<21)-1));
edges.emplace_back(u, v);
}
// Sanity: ensure exactly N-1
// (If not, still output what we have; the grader will judge.)
// But the algorithm constructs exactly N-1 unique edges.
for (auto &e : edges) {
Bridge(e.first, e.second);
}
}
};
void Solve(int N) {
Reconstructor rec(N);
rec.run();
}
