#include "highway.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<pair<int,int>> adj[N];
vector<pair<int,int>> adj2[N];
int vis[N];
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
int m = u.size();
vector<int> w(m,0);
long long len = ask(w) / a;
int l = 0,r = m-1;
while(l < r){
int m = (l + r)/2;
for(int i = l;i<=m;i++){
w[i] = 1;
}
if(ask(w) != len * a){
for(int i = l;i<=m;i++){
w[i] = 0;
}
r = m;
}
else l = m + 1;
}
for(int i = 0;i<m;i++){
adj[u[i]].push_back({v[i],i});
adj[v[i]].push_back({u[i],i});
}
// cout << "EDGE:";
// cout << u[l] << ' ' << v[l] << endl;
queue<int> q;
vis[u[l]] = 1;
vis[v[l]] = 1;
q.push(u[l]);
q.push(v[l]);
while(q.size()){
auto tp = q.front();
q.pop();
for(auto u:adj[tp]){
if(vis[u.first]){
continue;
}
vis[u.first] = 1;
adj2[tp].push_back(u);
q.push(u.first);
}
}
function<void(int)> dfs = [&](int v)->void{
for(auto u:adj2[v]){
w[u.second] = 0;
dfs(u.first);
}
};
w.assign(m,1);
dfs(u[l]);
long long dep1 = (len * b - ask(w))/(b-a);
long long dep2 = len - 1 - dep1;
// cout <<"DEP";
// cout << dep1 << ' ' << dep2 << endl;
function<void(int,int,vector<pair<int,int>> &)> dfs2 = [&](int v,int target,vector<pair<int,int>> &x)->void{
for(auto u:adj2[v]){
if(target > 0)
w[u.second] = 0;
if(target == 1){
x.push_back(u);
}
dfs2(u.first,target - 1,x);
}
};
int s = -1;
int t = -1;
if(dep1 == 0)
s = u[l];
if(dep2 == 0)
t = v[l];
if(s == -1){
vector<pair<int,int>> x;
w.assign(m,1);
dfs2(u[l],dep1,x);
while(x.size() > 1){
vector<pair<int,int>> tmp;
while(tmp.size() < x.size()){
tmp.push_back(x.back());
x.pop_back();
}
for(auto u:tmp){
w[u.second] = 1;
}
if(ask(w) != (dep2 + 1) * b + dep1 * a){
for(auto u:tmp){
w[u.second] = 0;
}
x = tmp;
}
}
s = x[0].first;
}
if(t == -1){
vector<pair<int,int>> x;
w.assign(m,1);
dfs2(v[l],dep2,x);
// cout << "CAND:";
// for(auto u:x){
// cout << u.first << ' ';
// }
// cout << endl;
while(x.size() > 1){
vector<pair<int,int>> tmp;
while(tmp.size() < x.size()){
tmp.push_back(x.back());
x.pop_back();
}
for(auto u:tmp){
w[u.second] = 1;
}
if(ask(w) != (dep1 + 1) * b + dep2 * a){
for(auto u:tmp){
w[u.second] = 0;
}
x = tmp;
}
}
t = x[0].first;
}
// cout << "HEY";
// cout << s << ' ' << t << endl;
answer(s,t);
}
/*
7 6 4 18 2 3
1 0
2 0
3 0
4 1
5 2
6 5
*/
