#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct E {
int to, i;
};
const int N = 1e5 + 5;
vector<E> g[N], ord;
int anc[N];
void dfs(int node) {
for (E e : g[node]) {
if (e.to != anc[node]) {
ord.push_back(e);
anc[e.to] = node;
dfs(e.to);
}
}
}
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
int m = u.size();
for (int i = 0; i < m; i++) {
g[u[i]].push_back({v[i], i});
g[v[i]].push_back({u[i], i});
}
ll dist = ask(vector<int>(m, 0)) / a;
dfs(0);
// for (E e : ord) {
// cout << e.to << " ";
// }
// cout << "\n";
int s, t;
int l = -1, r = ord.size() - 1;
while (r - l > 1) {
int p = (l + r) >> 1;
vector<int> w(m);
for (int i = 0; i <= p; i++)
w[ord[i].i] = 1;
if (ask(w) == dist * b)
r = p;
else
l = p;
}
s = ord[r].to;
l = -1, r = ord.size() - 1;
while (r - l > 1) {
int p = (l + r) >> 1;
vector<int> w(m);
for (int i = 0; i <= p; i++)
w[ord[i].i] = 1;
if (ask(w) > dist * a)
r = p;
else
l = p;
}
int lca = anc[ord[r].to];
// cout << lca << " " << s << "\n";
int x = s;
ll half = 0;
while (x != lca) {
half++;
x = anc[x];
}
if (half == dist) {
t = lca;
}
else {
l = -1, r = ord.size() - 1;
while (r - l > 1) {
int p = (l + r) >> 1;
vector<int> w(m);
for (int i = 0; i <= p; i++)
w[ord[i].i] = 1;
if (ask(w) >= dist * a + (dist - half) * (b - a))
r = p;
else
l = p;
}
t = ord[r].to;
}
answer(s, t);
}
