#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
vector<vector<pair<int, int>>> adjlist;
vector<int> ei, pre, visited, spec;
void dfs(int n) {
visited[n] = 1;
pre[n] = cnt++;
for (auto i : adjlist[n]) {
if (visited[i.first]) continue;
ei[i.first] = i.second;
spec[i.first] = spec[n];
dfs(i.first);
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
adjlist.resize(N, vector<pair<int, int>>());
ei.resize(N, -1);
pre.resize(N, 0);
spec.resize(N, 0);
visited.resize(N, 0);
int M = U.size();
for (int i = 0; i < M; i++) {
adjlist[U[i]].push_back({ V[i], i });
adjlist[V[i]].push_back({ U[i], i });
}
vector<int> w(M, 0);
int pl = ask(w) / A;
int low = 0, high = M - 1, ans = -1;
while (low <= high) {
int x = (low + high) / 2;
w = vector<int>(M, 0);
for (int i = 0; i <= x; i++) w[i] = 1;
int res = ask(w);
if (res != A * pl) ans = x, high = x - 1;
else low = x + 1;
}
spec[V[ans]] = 1;
dfs(U[ans]);
vector<int> special, notspecial;
for (int i = 0; i < N; i++) {
if (spec[i]) special.push_back(i);
else notspecial.push_back(i);
}
sort(special.begin(), special.end(), [](auto a, auto b) {return pre[a] < pre[b]; });
sort(notspecial.begin(), notspecial.end(), [](auto a, auto b) {return pre[a] < pre[b]; });
low = 0, high = special.size() - 1;
int ans1 = -1, ans2 = -1;
w = vector<int>(M, 1);
for (int i = 1; i < N; i++) w[ei[i]] = 0;
while (low <= high) {
int x = (low + high) / 2;
vector<int> _w = w;
for (int i = 1; i <= x; i++) _w[ei[special[i]]] = 1;
int res = ask(w);
if (res != A * pl) ans1 = x, high = x - 1;
else low = x + 1;
}
low = 0, high = notspecial.size() - 1;
while (low <= high) {
int x = (low + high) / 2;
vector<int> _w = w;
for (int i = 1; i <= x; i++) _w[ei[notspecial[i]]] = 1;
int res = ask(w);
if (res != A * pl) ans2 = x, high = x - 1;
else low = x + 1;
}
answer(special[ans1], notspecial[ans2]);
}
