#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
const int MOD = 1e9 + 7;
#define F first
#define S second
#define sz(x) int((x).size())
#define sor(x) sort(begin(x), end(x))
#define FOR(i, a, b) for (int i = a; i < b; i++)
map<int,vector<pi>> Adj;
vi Anc, Candidates;
vector<ll> Depths;
ll depth;
void dfs(int u, int pre) {
Depths[u] = Depths[pre] + 1;
if (Depths[u] == depth) Candidates.push_back(u);
for (auto v : Adj[u]) {
if (v.F == pre) continue;
Anc[v.F] = v.S;
dfs(v.F, u);
}
}
void find_pair(int n, vi U, vi V, int a, int b) {
int m = U.size();
int s = 0;
vi traffic(m, 0);
depth = ask(traffic) / (ll)a;
//cout << "depth is " << depth << endl;
Depths.resize(n, -1);
Anc.resize(n);
Anc[0] = -1;
FOR(i, 0, m) {
Adj[U[i]].push_back({V[i],i});
Adj[V[i]].push_back({U[i],i});
}
dfs(0, 0);
//for (auto anc : Anc) cout << anc << " "; cout << endl;
//for (auto d : Depths) cout << d << " "; cout << endl;
while (sz(Candidates) > 1) {
//for (auto c : Candidates) cout << c << " "; cout << "oink" << endl;
vi traffic(m, 0), Left, Right;
int k = sz(Candidates);
FOR(i, 0, k / 2) {
traffic[Anc[Candidates[i]]] = 1;
Left.push_back(Candidates[i]);
}
FOR(i, k / 2, k) {
Right.push_back(Candidates[i]);
}
ll toll = ask(traffic);
if (toll > depth * (ll)a) {
Candidates = Left;
}
else {
Candidates = Right;
}
}
answer(s, Candidates[0]);
}
//#include "grader.cpp"
