#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ar2 = array<int,2>;
const int INF = (int)1e9;
const ll LINF = (ll)2e18;
const int mxN = (int)2e5+10;
int n, m, dep[mxN];
ll A, B, dis;
int st[mxN], dfs_tim;
vector<ar2> adj[mxN], potential_edges;
vi w, edges;
void init(){
dfs_tim = 0;
edges.clear();
potential_edges.clear();
}
void dfs(int s, int p){
st[s] = dfs_tim++;
if(p!=-1) dep[s] = dep[p]+1;
else dep[s] = 0;
for(auto [u,i] : adj[s]){
if(u==p) continue;
edges.pb(i); dfs(u,s);
if(dep[s]+1==dis) potential_edges.pb({i,u});
}
}
bool chk(int x){
for(int i = sz(edges)-1; i >= x; i--) w[edges[i]]=1;
ll toll = ask(w);
for(int i = sz(edges)-1; i >= x; i--) w[edges[i]]=0;
return (toll!=A*dis);
}
bool chk2(int x){
for(int i = 0; i <= x; i++) w[potential_edges[i][0]]=1;
ll toll = ask(w);
for(int i = 0; i <= x; i++) w[potential_edges[i][0]]=0;
return (toll!=A*dis);
}
void find_pair(int N, vi U, vi V, int _A, int _B) {
n = N, m = sz(U); w.resize(m,0);
A=_A, B=_B; dis = ask(w)/A;
for(int i = 0; i < m; i++){
int a = U[i], b = V[i];
adj[a].pb({b,i});
adj[b].pb({a,i});
}
init(); dfs(0,-1);
int s=0, t=0;
int l = 0, r = sz(edges)-1;
while(l<r){
int mid = (l+r+1)/2;
if(chk(mid)) l=mid;
else r=mid-1;
}
s = edges[l];
if(st[U[s]] > st[V[s]]) s=U[s];
else s=V[s];
init(); dfs(s,-1);
l = 0, r = sz(potential_edges)-1;
while(l<r){
int mid = (l+r)/2;
if(chk2(mid)) r=mid;
else l=mid+1;
}
t = potential_edges[l][1];
if(s>t) swap(s,t);
answer(s, t); return;
}
