#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mxn = 9e4 + 5;
int in[mxn], timer = 0;
vector<int> tour;
vector<pii> g[mxn];
void dfs(int u, int p) {
in[u] = timer++;
tour.push_back(u);
for(auto [v, id] : g[u])
if(v ^ p) dfs(v, u);
}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
int m = U.size();
ll len = ask(vector<int>(m)) / A;
for(int i=0; i<m; i++) {
g[U[i]].push_back({ V[i], i });
g[V[i]].push_back({ U[i], i });
}
dfs(0, 0);
for(int i=0; i<m; i++)
if(in[U[i]] > in[V[i]]) swap(U[i], V[i]);
int l=0, r=n-1, p=0;
while(l <= r) {
int mid = (l + r) / 2;
vector<int> to_get(m, 1);
for(int i=0; i<m; i++)
if(in[V[i]] <= mid) to_get[i] = 0;
if(ask(to_get) == len * A) p = mid, r = mid - 1;
else l = mid + 1;
}
int S = tour[p];
timer = 0;
tour.clear();
dfs(S, S);
for(int i=0; i<m; i++) {
if(in[U[i]] > in[V[i]]) swap(U[i], V[i]);
// cout << U[i] << " " << V[i] << endl;
}
l=0, r=n-1, p=0;
while(l <= r) {
int mid = (l + r) / 2;
vector<int> to_get(m, 1);
for(int i=0; i<m; i++)
if(in[V[i]] <= mid) to_get[i] = 0;
if(ask(to_get) == len * A) p = mid, r = mid - 1;
else l = mid + 1;
}
int T = tour[p];
// cout << S << " " << T << endl;
answer(S, T);
}
