#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
vector<vector<pair<int, int>>> adj;
vector<pair<int, int>> sorted;
vector<bool> vst;
vector<int> nDist;
void dfs(int a, int dist) {
if (vst[a]) return;
vst[a] = true;
nDist[a] = dist - 1;
for (auto &e : adj[a]) {
if (vst[e.first]) continue;
sorted.push_back({dist, e.second});
dfs(e.first, dist + 1);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
adj = vector<vector<pair<int, int>>>(N);
sorted = vector<pair<int, int>>();
for (int i = 0; i < M; i++) {
adj[U[i]].push_back({V[i], i});
adj[V[i]].push_back({U[i], i});
}
vst = vector<bool>(N);
nDist = vector<int>(N);
dfs(0, 1);
sort(sorted.begin(), sorted.end());
vector<int> tst(M);
ll ctrl = ask(tst);
int begin = 0;
int end = M - 1;
while (begin < end) {
vector<int> w(M);
int mid = (begin + end + 1) / 2;
for (int i = mid; i <= end; i++) {
w[sorted[i].second] = 1;
}
ll res = ask(w);
if (res > ctrl) {
begin = mid;
}
else {
end = mid - 1;
}
}
pair<int, int> sEdge = sorted[begin];
int S = 0;
for (int i = 0; i < N; i++) {
bool hasS = false, further = nDist[i] == sEdge.first;
for (auto &e : adj[i]) {
if (e.second == sEdge.second) hasS = true;
}
if (hasS && further) {
S = i;
break;
}
}
//cout << S << '\n';
vst = vector<bool>(N);
nDist = vector<int>(N);
sorted = vector<pair<int, int>>();
dfs(S, 1);
sort(sorted.begin(), sorted.end());
begin = -1;
for (int i = 0; i < M; i++) {
if (sorted[i].first == ctrl / A && begin == -1) begin = i;
if (sorted[i].first == ctrl / A) end = i;
}
while (begin < end) {
vector<int> w(M);
int mid = (begin + end + 1) / 2;
for (int i = mid; i <= end; i++) {
w[sorted[i].second] = 1;
}
ll res = ask(w);
if (res > ctrl) {
begin = mid;
}
else {
end = mid - 1;
}
}
pair<int, int> tEdge = sorted[begin];
int T = 0;
for (int i = 0; i < N; i++) {
bool hasT = false, further = nDist[i] == tEdge.first;
for (auto &e : adj[i]) {
if (e.second == tEdge.second) hasT = true;
}
if (hasT && further) {
T = i;
break;
}
}
answer(S, T);
}
