#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){
return a.size();
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<vector<int>> g;
vector<int> u, v;
int n, m;
vector<int> nodes, ch;
void dfs(int tar, int i, int p = -1, int d = 0){
for(auto j : g[i]){
int x = u[j] ^ v[j] ^ i;
if(x == p) continue;
if(d + 1 == tar){
nodes.push_back(j);
ch.push_back(x);
}else{
dfs(tar, x, i, d + 1);
}
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int a, int b) {
n = N;
u = U;
v = V;
m = len(v);
g.resize(n);
for(int i = 0; i < m; i ++){
g[u[i]].push_back(i);
g[v[i]].push_back(i);
}
vector<int> w(m, 1);
ll d = ask(w) / b;
queue<int> q;
q.push(0);
vector<int> vis(n);
vector<int> ord;
vis[0] = 1;
while(!q.empty()){
int t = q.front(); q.pop();
for(auto j : g[t]){
int x = u[j] ^ v[j] ^ t;
if(vis[x]) continue;
ord.push_back(j);
ch.push_back(x);
vis[x] = 1;
q.push(x);
}
}
int l = -2, r = n - 2;
while(r - l > 1){
int mid = (l + r) / 2;
for(int j = 0; j <= mid; j ++){
w[ord[j]] = 0;
}
for(int j = mid + 1; j < n - 1; j ++) w[ord[j]] = 1;
if(d * a == ask(w)){
r = mid;
}else l = mid;
}
int s = (r == -1 ? 0 : ch[r]);
ch.clear();
dfs(d, s);
l = -1, r = len(ch) - 1;
w.assign(m, 1);
while(r - l > 1){
int mid = (l + r) / 2;
for(int j = 0; j <= mid; j ++){
w[nodes[j]] = 0;
}
for(int j = mid + 1; j < len(ch); j ++){
w[nodes[j]] = 1;
}
if(ask(w) != d * b){
r = mid;
}else l = mid;
}
answer(s, ch[r]);
}
