#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 90010;
vector <pair <int, int>> g[N];
pair <int, int> especial;
vector <int> query;
pair <int, int> pai[N];
int h[N];
int t1;
vector <array <int, 3>> arestas;
void dfs(int v, int p){
for(auto [x, idx] : g[v]){
if(x == p) continue;
query[idx] = 1;
dfs(x, v);
}
return;
}
void dfs2(int v, int p){
for(auto [x, idx] : g[v]){
if(x == p) continue;
h[x] = h[v]+1;
pai[x] = {v, idx};
if(h[x] == t1) arestas.push_back({x, v, idx});
dfs2(x, v);
}
return;
}
void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B) {
int m = u.size();
for(int i = 0;i < m;i++){
int a = u[i], b = v[i];
g[a].push_back({b, i});
g[b].push_back({a, i});
}
for(int i = 0;i < m;i++){
query.push_back(0);
}
int h = ask(query)/A;
int l = 0, r = m-1;
while(l < r){
int mid = (l+r)/2;
for(int i = l;i <= mid;i++){
query[i] = 1;
}
int t = ask(query);
for(int i = l;i <= mid;i++){
query[i] = 0;
}
if(t > h*A){
r = mid;
}
else{
l = mid+1;
}
}
especial = {u[l], v[l]};
dfs(u[l], v[l]);
// cout << u[l] << ' ' << v[l] << endl;
int S = ask(query);
t1 = (S-A*h)/(B-A);
//// cout << t1 << endl;
int ll = l;
for(int i = 0;i < m;i++){
query[i] = 0;
}
pair <int, int> resposta;
if(t1 == 0) resposta.first = u[ll];
else{
dfs2(u[ll], v[ll]);
l = 0; r = arestas.size()-1;
// cout << t1 << endl;
for(auto [a, b, c] : arestas){
// cout << a << ' ' << b << ' ' << c << endl;
}
while(l < r){
int mid = (l+r)/2;
for(int i = l;i <= mid;i++){
query[arestas[i][2]] = 1;
}
int t = ask(query);
for(int i = l;i <= mid;i++){
query[arestas[i][2]] = 0;
}
// cout << t << endl;
if(t > h*A){
r = mid;
}
else{
l = mid+1;
}
}
resposta.first = arestas[l][0];
}
//// cout << resposta.first << endl;
arestas.clear();
t1 = h-t1-1;
swap(u[ll], v[ll]);
// cout << u[ll] << ' ' << v[ll] << endl;
if(t1 == 0) resposta.second = u[ll];
else{
dfs2(u[ll], v[ll]);
l = 0; r = arestas.size()-1;
while(l < r){
int mid = (l+r)/2;
for(int i = l;i <= mid;i++){
query[arestas[i][2]] = 1;
}
int t = ask(query);
for(int i = l;i <= mid;i++){
query[arestas[i][2]] = 0;
}
if(t > h*A){
r = mid;
}
else{
l = mid+1;
}
}
resposta.second = arestas[l][0];
}
// cout << resposta.first << ' ' << resposta.second << endl;
answer(resposta.first, resposta.second);
return;
}
