#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cerr << #x << ": " << x << "\n";
vector<pair<int, int>> depth, path;
vector<vector<pair<int, int>>> arr;
void dfs(int node, int prev = -1){
for(const auto &i : arr[node]){
if(i.first == prev) continue;
path.push_back({i.first, i.second});
depth[i.first] = {depth[node].first + 1, i.second};
dfs(i.first, node);
}
}
int max_depth(int a, int b){
if(depth[a].first > depth[b].first) return a;
return b;
}
int min_depth(int a, int b){
if(depth[a].first < depth[b].first) return a;
return b;
}
pair<int, int> solve(int dis2, int dis1, 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) {
depth.assign(N, {0, 0});
arr.assign(N, vector<pair<int, int>>());
vector<int> pos_ans;
vector<int> vec(U.size(), 0);
long long dis = ask(vec);
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});
}
pair<int, int> root;
for(int i = 0; i < (int)arr.size(); i++){
if(arr[i].size() == 1){
root = {i, arr[i][0].second};
break;
}
}
dfs(root.first);
int l = 0, r = U.size(), m;
ll dis2 = 0;
while(l + 1 < r){
m = (l + r) / 2;
vec.assign(U.size(), 0);
for(int i = 0; i < m; i++)
vec[path[i].second] = 1;
dis2 = ask(vec);
if(dis2 != dis){
if(dis2 / B == dis / A){
r = m;
continue;
}
break;
}
l = m;
}
// solve returns {x, y};
// y --- m --- x
m = (l + r) / 2;
pair<int, int> dism = solve(dis2, dis, A, B);
int mid = min_depth(U[path[m].second], V[path[m].second]), s = 0, t = 0;
for(int i = 0; i < N; i++){
if(depth[i].first == depth[mid].first - dism.second) s = i;
if(depth[i].first == depth[mid].first + dism.first) t = i;
}
answer(s, t);
}
