#include "highway.h"
#include <iostream>
using namespace std;
vector<vector<pair<int, int>>> g;
vector<int> parent, edgeUp, depth;
void rootDFS(int node, int d = 0, int eUP = -1, int par = -1) {
parent[node] = par;
edgeUp[node] = eUP;
depth[node] = d;
for (auto [child, e] : g[node]) {
if (child != par) rootDFS(child, d+1, e, node);
}
}
void rootTree(int root, int N) {
parent.resize(1+N);
edgeUp.resize(1+N);
depth.resize(1+N);
rootDFS(root);
}
vector<int> nodesDepth(int d) {
vector<int> v;
for (int i = 0; i < (int)depth.size(); ++i) {
if (depth[i] == d) v.push_back(i);
}
return v;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
g.resize(1+N);
int M = U.size();
for (int i = 0; i < M; ++i) {
g[U[i]].emplace_back(V[i], i);
g[V[i]].emplace_back(U[i], i);
}
vector<int> w(M);
long long toll = ask(w);
// Solve for tree, one end is known
int S = 0;
rootTree(S, N);
vector<int> candidates = nodesDepth(toll/A);
int l = 0, r = (int)candidates.size(); // in range [l, r)
while (l+1 < r) {
int mid = (l+r)/2;
for (int i = mid; i < r; ++i) w[edgeUp[candidates[i]]] = 1;
int res = ask(w);
for (int i = mid; i < r; ++i) w[edgeUp[candidates[i]]] = 0;
if (res == toll) r = mid;
else l = mid;
}
int T = candidates[l];
answer(S, T);
}
