#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cerr << #x << ": " << x << "\n";
#define dbgv(x) cerr << #x << ": "; for(auto &i : x) cout << i << ' '; cout << "\n";
vector<vector<pair<int, int>>> arr;
vector<int> depth, path;
void dfs(int node, int prev = -1){
for(const auto &i : arr[node]){
if(i.first == prev) continue;
depth[i.first] = depth[node] + 1;
path.push_back(i.second);
dfs(i.first, node);
}
}
pair<int, int> idk(ll dis1, ll dis2, int A, int B){
int x, y;
y = (dis2 - dis1) / (B - A);
x = dis1 / A - y;
return {x, y};
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
arr.assign(N, vector<pair<int, int>>());
depth.assign(N, 0);
for(int i = 0; i < (int)U.size(); i++){
arr[U[i]].push_back({V[i], i});
arr[V[i]].push_back({U[i], i});
}
int root = 0;
for(int i = 0; i < N; i++){
if(arr[i].size() == 1){
root = i;
break;
}
}
dfs(root);
//dbgv(path);
//dbgv(depth);
vector<int> vec(N - 1, 0);
int s = 0, t = 0, l = 0, r = N - 1, m = (l + r) / 2;
long long dis1 = ask(vec), dis2 = 0;
while(l + 1 < r){
m = (l + r) / 2;
for(int i = l; i < m; i++){
vec[path[i]] = 1;
}
dis2 = ask(vec);
if(dis2 / B == dis1 / A){
vec.assign(N - 1, 0);
r = m;
continue;
}
if(dis2 == dis1){
l = m;
continue;
}
break;
}
pair<int, int> ans = idk(dis1, dis2, A, B);
int disl = ans.second, disr = ans.first;
//dbg(m);
//dbg(disl);
//dbg(disr);
//dbg(dis1);
//dbg(dis2);
for(int i = 0; i < N; i++){
if(depth[i] == m + disr){
s = i;
continue;
}
if(depth[i] == m - disl){
t = i;
continue;
}
}
answer(s, t);
}
