#include "highway.h"
#include<bits/stdc++.h>
using namespace std ;
const int N = 9e4 + 4 ;
long long ds[N] , vis[N] , vid , par[N];
vector<int> adj[N];
int U , V ;
map<pair<int , int > , int > mp ;
vector<int> w ;
void bfs(int s){
memset(ds , 0 , sizeof ds);
ds[s] = 0 ;
vid ++ ;
queue<int> q ;
q.push(s);
vis[s] = vid ;
while(q.size()){
auto fr = q.front();
q.pop();
for(auto f : adj[fr]){
if(w[mp[{fr , f}]])continue ;
if(vid != vis[f]){
vis[f] = vid ;
q.push(f);
par[f] = fr ;
ds[f] = ds[fr] + 1 ;
}
}
}
}
void dfs(int u , int p , int number){
for(auto f : adj[u]){
if(f != p){
w[mp[{u , f}]] = number ;
dfs(f , u , number);
}
}
}
void find_pair(int N, std::vector<int> u, std::vector<int> v, int A, int B) {
int M = u.size() , n = N ;
for(int i = 0 ; i < M ; i ++)
adj[u[i]].push_back(v[i]) , adj[v[i]].push_back(u[i]) , mp[{u[i] , v[i]}] = mp[{v[i] , u[i]}] = i;
w = vector<int> (M , 0);
long long toll = ask(w) , d = toll / A;
vector<int> edges;
for(int i = 0 ; i < M ; i ++)
edges.push_back(i);
int l = 0 , r = M - 1 , md ;
while(l < r){
md = (l + r) / 2 ;
//cout << l << " " << md << " " << r << endl ;
edges = vector<int> (M , 0);
for(int i = l ; i <= md ; i ++)
edges[i] = 1 ;
long long toll2 = ask(edges);
// cout << "DD" << toll << " " << toll2 << endl;
if(toll == toll2)l = md + 1 ;
else r = md ;
}
U = u[l] , V = v[l];
w = vector<int> (M , 0);
dfs(U , V , 1);
long long toll2 = ask(w);
// x + y = d
// Bx + Ay = toll2
long long va = B - A ;
long long v2 = B * d - toll2 ;
v2 /= va ;
int rest = d - v2 ;
bfs(V);
toll = toll2;
vector<int> poss ;
for(int i = 0 ; i < n; i ++){
if(i != U && ds[i] == v2 - 1 )poss.push_back(i);
}
l = 0 , r = poss.size() - 1 , md ;
while(l < r){
md = (l + r ) / 2 ;
//cout << l << " " << md << " " << r << endl;
w = vector<int> (M , 0);
dfs(U , V , 1);
for(int i = l ; i <= md ; i ++)
w[mp[{par[poss[i]] , poss[i]}]] = 1 ;
toll2 = ask(w);
if(toll == toll2)
l = md + 1 ;
else r = md ;
}
int s , t ;
s = poss[l];
swap(U , V);
w = vector<int> (M , 0);
dfs(U , V , 1);
toll2 = ask(w);
// x + y = d
// Bx + Ay = toll2
va = B - A ;
v2 = B * d - toll2 ;
v2 /= va ;
rest = d - v2 ;
bfs(V);
toll = toll2;
poss.clear();
for(int i = 0 ; i < n; i ++){
if(i != U && ds[i] == v2 - 1 )poss.push_back(i);
}
l = 0 , r = poss.size() - 1 , md ;
while(l < r){
md = (l + r ) / 2 ;
//cout << l << " " << md << " " << r << endl;
w = vector<int> (M , 0);
dfs(U , V , 1);
for(int i = l ; i <= md ; i ++)
w[mp[{par[poss[i]] , poss[i]}]] = 1 ;
toll2 = ask(w);
if(toll == toll2)
l = md + 1 ;
else r = md ;
}
t = poss[l];
answer(s, t);
}
