#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int timer = 0;
int tin[130001], pa[130001], id[130001];
int rv[130001];
vector<pair<int, int>> adj[130001];
void dfs(int u, int p) {
tin[u] = ++timer;
rv[timer] = u;
// cout << "dfs: " << u << '\n';
for (auto& [v, eid] : adj[u]) {
if (v == p) continue;
pa[v] = u, id[v] = eid;
dfs(v, u);
}
}
void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B) {
int m = u.size();
vector<int> w(m, 0);
ll dist = ask(w) / A;
for (int i = 0; i < m; i++) {
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
}
pa[0] = 0;
dfs(0, -1);
// answer(0, n - 1);
int l = 1, r = n;
while (l < r) {
int mid = (l + r) / 2;
w = vector<int>(m, 0);
for (int i = 1; i <= mid; i++) {
int node = rv[i];
if (node != 0) w[id[node]] = 1;
}
ll res = ask(w);
if (1LL * B * dist == res) r = mid;
else l = mid + 1;
}
int T = rv[l];
// cout << T << '\n';
timer = 0;
for (int i = 0; i <= 130000; i++) tin[i] = pa[i] = id[i] = rv[i] = 0;
pa[T] = T;
dfs(T, -1);
l = 1, r = n;
while (l < r) {
int mid = (l + r) / 2;
w = vector<int>(m, 0);
for (int i = 1; i <= mid; i++) {
int node = rv[i];
if (node != T) w[id[node]] = 1;
}
ll res = ask(w);
if (1LL * B * dist == res) r = mid;
else l = mid + 1;
}
int S = rv[l];
// cout << S << '\n';
answer(S, T);
}
