#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define out(o) cout << o
vector<vector<pair<int, int>>> adjList;
vector<int> parent;
vector<vector<int>> level;
void dfs(int v, int p, int i, int l) {
parent[v] = i;
level[l].push_back(v);
for (auto con: adjList[v]) {
if (con.first == p) continue;
dfs(con.first, v, con.second, l + 1);
}
}
vector<int> correct;
vector<int> upward;
int d;
void comp(int v, int p, int i, int h) {
if (h == d) {
correct.push_back(v);
upward.push_back(i);
}
for (auto con: adjList[v]) {
if (con.first == p) continue;
comp(con.first, v, con.second, h + 1);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size(); // = V.size(); assumed to be N - 1
adjList.resize(N);
parent.resize(N);
level.resize(N);
for (int i = 0; i < M; i++) {
int a = U[i];
int b = V[i];
adjList[a].push_back({b, i});
adjList[b].push_back({a, i});
}
vector<int> W(N - 1, 0);
long long dw = ask(W);
d = (int) (dw / ((long long) A));
dfs(0, -1, -1, 0);
int l = 1;
int r = N;
while (r - l > 1) {
int middle = (l + r) / 2;
vector<int> W(N - 1, 0);
for (int le = middle; le < N; le++) for (int node: level[le]) W[parent[node]] = 1;
long long here = ask(W);
if (here > dw) l = middle;
else r = middle;
}
int HEIGHT = l;
l = 0;
r = level[HEIGHT].size();
while (r - l >= 1) {
int middle = (l + r) / 2;
vector<int> W(N - 1, 0);
for (int i = 0; i <= middle; i++) W[parent[level[HEIGHT][i]]] = 1;
long long here = ask(W);
if (here > dw) r = middle;
else l = middle + 1;
}
int first = level[HEIGHT][l];
comp(first, -1, -1, 0);
l = 0;
r = correct.size();
while (r - l >= 1) {
int middle = (l + r) / 2;
vector<int> W(N - 1, 0);
for (int i = 0; i <= middle; i++) W[upward[i]] = 1;
long long here = ask(W);
if (here > dw) r = middle;
else l = middle + 1;
}
int second = correct[l];
answer(first, second);
}
