#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll edge_dist, max_dist, min_dist;
ll find_max_depth(ll n, ll a, ll b, vector<ll> &d, vector<ll> &edge){
ll lo = 0, hi = n-1;
while(lo < hi){
ll mid = (lo + hi) / 2;
vector<int> w(n-1);
for(ll i = 1; i < n; i++) if(d[i] <= mid) w[edge[i]] = 1;
if(ask(w) == max_dist) hi = mid;
else lo = mid+1;
}
return hi;
}
void calc_depth(ll n, ll p, vector<vector<pll>> &g, vector<ll> &d, vector<ll> &edge){
for(auto[i, edge_idx]: g[n]) if(i != p){
d[i] = d[n] + 1;
edge[i] = edge_idx;
calc_depth(i, n, g, d, edge);
}
}
ll find_start_node(ll n, ll depth, vector<ll> &d, vector<ll> &edge){
vector<ll> v;
for(ll i = 0; i < n; i++) if(d[i] == depth) v.push_back(i);
ll lo = 0, hi = v.size() - 1;
while(lo < hi){
ll mid = (lo + hi) / 2;
vector<int> w(n-1);
for(ll i = 0; i <= mid; i++) w[edge[v[i]]] = 1;
if(ask(w) > min_dist) hi = mid;
else lo = mid+1;
}
return v[hi];
}
ll find_end_node(ll n, ll s, vector<ll> &d, vector<ll> &edge){
vector<ll> v;
for(ll i = 0; i < n; i++) if(d[i] == edge_dist) v.push_back(i);
ll lo = 0, hi = v.size() - 1;
while(lo < hi){
ll mid = (lo + hi) / 2;
vector<int> w(n-1);
for(ll i = 0; i <= mid; i++) w[edge[v[i]]] = 1;
if(ask(w) > min_dist) hi = mid;
else lo = mid+1;
}
return v[hi];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
ll n = N, a = A, b = B, m = U.size();
vector<vector<pll>> g(n);
for(ll i = 0; i < m; i++) g[U[i]].push_back({V[i], i}), g[V[i]].push_back({U[i], i});
vector<int> full(n-1, 1);
edge_dist = ask(full) / b;
min_dist = edge_dist * a, max_dist = edge_dist * b;
vector<ll> d(n), edge(n), dist_from_s(n);
calc_depth(0, -1, g, d, edge);
ll max_depth = find_max_depth(n, a, b, d, edge);
ll s = find_start_node(n, max_depth, d, edge);
calc_depth(s, -1, g, dist_from_s, edge);
ll t = find_end_node(n, s, dist_from_s, edge);
answer(s, t);
}
