#include "highway.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
#define pob pop_back()
#define iter(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
int n;
int m;
vector<vector<pii>> g;
vector<int> pr, pre, dpt;
vector<int> leaf;
ll query(int rt, int to){
vector<int> q(m);
while(to != rt){
q[pre[to]] = 1;
to = pr[to];
}
return ask(q);
}
ll query(int rt, int l, int r, vector<int>& v){
vector<int> q(m);
vector<int> tos;
for(int i = l; i <= r; i++) tos.eb(v[i]);
for(int to : tos){
while(to != rt){
q[pre[to]] = 1;
to = pr[to];
}
}
return ask(q);
}
int up(int from, int x){
while(x--){
from = pr[from];
}
return from;
}
void dfs(int now, int p, int e, int d){
pr[now] = p;
pre[now] = e;
dpt[now] = d;
bool child = false;
for(pii i : g[now]){
if(i.F == p) continue;
dfs(i.F, now, i.S, d + 1);
child = true;
}
if(!child) leaf.eb(now);
}
void find_pair(int N, vector<int> U, vector<int> V, int a, int b) {
n = N;
m = U.size();
assert(m == n - 1);
g.resize(n);
pr.resize(n);
pre.resize(n);
dpt.resize(n);
for(int i = 0; i < m; i++){
int u = U[i], v = V[i];
g[u].eb(mp(v, i));
g[v].eb(mp(u, i));
}
vector<int> XD(m);
ll dis = ask(XD);
dfs(0, 0, -1, 0);
int l = 0, r = (int)leaf.size() - 1;
while(l < r){
int mid = (l + r) / 2;
if(query(0, l, mid, leaf) != dis) r = mid;
else l = mid + 1;
}
int tmp = leaf[l];
l = 0, r = dpt[tmp];
while(l < r){
int mid = (l + r) / 2;
if(query(0, up(tmp, mid)) != dis) r = mid;
else l = mid + 1;
}
int v1 = up(tmp, l);
leaf.clear();
dfs(v1, v1, -1, 0);
vector<int> v;
for(int i = 0; i < n; i++){
if(dpt[i] == dis / a) v.eb(i);
}
l = 0, r = (int)v.size() - 1;
while(l < r){
int mid = (l + r) / 2;
if(query(v1, l, mid, v) != dis) r = mid;
else l = mid + 1;
}
int v2 = v[l];
answer(v1, v2);
}
