#include <bits/stdc++.h>
#define pb push_back
//#define int long long
using namespace std;
#include "highway.h"
vector<vector<pair<int, int> > > adj;
vector<vector<int> > depth;
vector<int> d, topar, p;
int mxdep;
void dfs(int node, int par){
if(node != par) d[node] = d[par] + 1;
p[node] = par;
mxdep = max(mxdep, d[node]);
depth[d[node]].pb(node);
for(auto itr: adj[node]){
if(itr.first == par) continue;
topar[itr.first] = itr.second;
dfs(itr.first, node);
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
adj.resize(N);
d.resize(N);
depth.resize(N);
topar.resize(N);
p.resize(N);
mxdep = 0;
for(int i = 0; i < M; i++){
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i});
}
dfs(0, 0);
vector<int> w(M, 0);
long long dis = ask(w); // QUERY
long long ec = dis / A;
int l = 1, r = mxdep;
while(l < r){
int m = (l + r + 1)/2;
for(int i = 0; i < M; i++) w[i] = 0;
for(int i = m; i <= mxdep; i++){
for(auto itr: depth[i]){
w[topar[itr]] = 1;
}
}
long long check = ask(w);
if(check == dis) r = m - 1;
else l = m;
} // LOG N QUERY
for(int i = 0; i < M; i++) w[i] = 0;
for(int i = l; i <= mxdep; i++){
for(auto itr: depth[i]){
w[topar[itr]] = 1;
}
}
long long val = ask(w); // QUERY
bool samedep = 0;
if(val - dis > (B - A)) samedep = 1;
int dep2 = l;
if(samedep){
vector<int> ans, vis(N);
for(int dene = 0; dene < 2; dene++){
vector<int> bsat;
for(auto itr: depth[dep2]){
if(!vis[itr]){
bsat.pb(itr);
}
}
l = 0, r = bsat.size()-1;
while(l < r){
int m = (l + r)/2;
for(int i = 0; i < M; i++) w[i] = 0;
for(int i = l; i <= m; i++){
w[topar[bsat[i]]] = 1;
}
long long check = ask(w);
if(check > dis) r = m;
else l = m + 1;
} // LOG N QUERY
ans.pb(bsat[l]);
vis[bsat[l]] = 1;
}
answer(ans[0], ans[1]);
}
else{
int ans2;
l = 0, r = depth[dep2].size()-1;
while(l < r){
int m = (l + r)/2;
for(int i = 0; i < M; i++) w[i] = 0;
for(int i = l; i <= m; i++){
w[topar[depth[dep2][i]]] = 1;
}
long long check = ask(w);
if(check > dis) r = m;
else l = m + 1;
} // LOG N QUERY
ans2 = depth[dep2][l];
vector<int> vis(N);
bool lcais1 = 0;
int x = ans2;
for(int i = 0; i < M; i++) w[i] = 0;
while(x != 0){
vis[x] = 1;
w[topar[x]] = 1;
x = p[x];
}
long long lcacheck = ask(w); // QUERY
int lcadep;
if(lcacheck == ec * B) lcais1 = 1;
else{
int side2ec = (lcacheck - dis) / (B - A);
lcadep = dep2 - side2ec;
}
if(lcais1){
int ans1 = ans2;
for(int i = 0; i < ec; i++) ans1 = p[ans1];
answer(ans1, ans2);
}
else{
// ec == (dep2 - lcadep) + (dep1 - lcadep) -> ec == dep1 + dep2 - 2*lcadep
int dep1 = ec - dep2 + 2*lcadep;
vector<int> bsat;
for(auto itr: depth[dep1]){
if(!vis[itr]) bsat.pb(itr);
}
l = 0, r = bsat.size()-1;
while(l < r){
int m = (l + r)/2;
for(int i = 0; i < M; i++) w[i] = 0;
for(int i = l; i <= m; i++){
w[topar[bsat[i]]] = 1;
}
long long check = ask(w);
if(check > dis) r = m;
else l = m + 1;
} // LOG N QUERY
int ans1 = bsat[l];
answer(ans1, ans2);
}
}
//answer(0, N - 1); cevabı koy buraya
}
