#include "highway.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
#include<utility>
using namespace std;
typedef long long ll;
namespace{
int n, m;
int maxi = 0;
vector<vector<int>> deped;
vector<vector<pair<int, int>>> depv;
vector<int> dep;
vector<vector<pair<int, int>>> graph;
void dfs(int node, int parent){
dep[node] = dep[parent] + 1;
maxi = max(maxi, dep[node]);
for(auto &[x, id]: graph[node]){
if(x == parent){
depv[dep[node]].emplace_back(node, id);
continue;
}
deped[dep[node]].push_back(id);
dfs(x, node);
}
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B){
n = N;
m = (int)U.size();
assert(m == n - 1);
deped.resize(n + 1);
dep.resize(n + 1);
depv.resize(n + 1);
graph.resize(n + 1);
for(int i = 0; i < m; i++){
graph[U[i]].emplace_back(V[i], i);
graph[V[i]].emplace_back(U[i], i);
}
dfs(0, 0);
int l = 1, r = maxi - 1;
vector<int> que(m);
ll a = A, b = B;
ll len = ask(que) / a;
while(l < r){
int mid = (l + r) >> 1;
for(int i = 0; i < m; i++) que[i] = 0;
for(int i = 1; i <= mid; i++){
for(auto &id: deped[i]) que[id] = 1;
}
if(ask(que) == len * b) r = mid;
else l = mid + 1;
}
int mdep = l + 1;
l = 0, r = (int)depv[mdep].size() - 1;
while(l < r){
int mid = ((l + r) >> 1);
for(int i = 0; i < m; i++) que[i] = 0;
for(int i = 0; i <= mid; i++) que[depv[mdep][i].second] = 1;
if(ask(que) == len * a) l = mid + 1;
else r = mid;
}
int s = depv[mdep][l].first;
mdep = len + 1;
//cout << mdep << "\n";
vector<vector<pair<int, int>>>().swap(depv);
depv.resize(n + 1);
fill(dep.begin(), dep.end(), 0);
dfs(s, s);
l = 0, r = (int)depv[mdep].size() - 1;
while(l < r){
int mid = ((l + r) >> 1);
for(int i = 0; i < m; i++) que[i] = 0;
for(int i = 0; i <= mid; i++) que[depv[mdep][i].second] = 1;
if(ask(que) == len * a) l = mid + 1;
else r = mid;
}
int t = depv[mdep][l].first;
//cout << s << " " << t << "\n";
answer(s, t);
//answer(0, 1);
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp highway.cpp
