#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define isz(a) ((signed)a.size())
using ll = long long;
struct edge_t{
int u, v;
};
const int N = 90'000 + 5, M = 130'000 + 5;
int n, m;
int a, b;
vector <edge_t> edge;
vector <int> adj[N];
vector <int> vquery;
namespace subtask1234{
bool check(){
return m == n - 1;
}
int length_path;
int pv[N];
int pe[N];
int ctrtour, tour[N];
void dfs_tour(int u){
tour[ctrtour] = u;
ctrtour++;
for (auto i: adj[u]){
if (i == pe[u]){
continue;
}
auto v = u ^ edge[i].u ^ edge[i].v;
pv[v] = u;
pe[v] = i;
dfs_tour(v);
}
}
int solve_fixed(int s){
pv[s] = -1;
pe[s] = -1;
ctrtour = 0;
dfs_tour(s);
int lo = 1, hi = n - 1;
while (lo < hi){
int mid = (lo + hi) >> 1;
fill(vquery.begin(), vquery.end(), 0);
for (int pos = 1; pos <= mid; pos++){
vquery[pe[tour[pos]]] = 1;
}
if (ask(vquery) == (ll)length_path * b){
hi = mid;
}
else{
lo = mid + 1;
}
}
return tour[lo];
}
int depth[N];
void dfs_depth(int u){
for (auto i: adj[u]){
if (i == pe[u]){
continue;
}
int v = u ^ edge[i].u ^ edge[i].v;
pv[v] = u;
pe[v] = i;
depth[v] = depth[u] + 1;
dfs_depth(v);
}
}
int find_one(){
int root = 1;
pv[root] = -1;
pe[root] = -1;
depth[root] = 0;
dfs_depth(root);
int lo = 1, hi = *max_element(depth, depth + n);
while (lo < hi){
int mid = (lo + hi + 1) >> 1;
fill(vquery.begin(), vquery.end(), 0);
for (int u = 0; u < n; u++){
if (depth[u] >= mid){
vquery[pe[u]] = 1;
}
}
if (ask(vquery) == (ll)length_path * a){
hi = mid - 1;
}
else{
lo = mid;
}
}
vector <int> layer;
for (int u = 0; u < n; u++){
if (depth[u] == lo){
layer.emplace_back(u);
}
}
lo = 0; hi = isz(layer) - 1;
while (lo < hi){
int mid = (lo + hi) >> 1;
fill(vquery.begin(), vquery.end(), 0);
for (int i = 0; i <= mid; i++){
vquery[pe[layer[i]]] = 1;
}
if (ask(vquery) == (ll)length_path * a){
lo = mid + 1;
}
else{
hi = mid;
}
}
return layer[lo];
}
void solve(){
fill(vquery.begin(), vquery.end(), 0);
length_path = ask(vquery) / a;
int s = find_one();
int t = solve_fixed(s);
answer(s, t);
}
}
void find_pair(int _n, vector <int> _u, vector <int> _v, int _a, int _b){
n = _n;
m = isz(_u);
edge.resize(m);
for (int i = 0; i < m; i++){
int u = _u[i], v = _v[i];
edge[i] = edge_t{u, v};
adj[u].emplace_back(i);
adj[v].emplace_back(i);
}
a = _a;
b = _b;
vquery.resize(m);
if (subtask1234::check()){
subtask1234::solve();
return;
}
}
