#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;
if (spec[n]) spec[i.first] = 1;
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;
}
for (int i = 0; i < adjlist[U[ans]].size(); i++) if (adjlist[U[ans]][i].first == V[ans]) swap(adjlist[U[ans]][0], adjlist[U[ans]][i]);
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 = 1, high = special.size() - 1;
int ans1 = 0, ans2 = 0;
w = vector<int>(M, 1);
for (int i = 0; i < N; i++) if (i != U[ans]) w[ei[i]] = 0;
while (low <= high) {
int x = (low + high) / 2;
vector<int> _w = w;
for (int i = x; i < special.size(); i++) _w[ei[special[i]]] = 1;
int res = ask(_w);
if (res != A * pl) ans1 = x, low = x + 1;
else high = x - 1;
}
low = 1, high = notspecial.size() - 1;
while (low <= high) {
int x = (low + high) / 2;
vector<int> _w = w;
for (int i = x; i < notspecial.size(); i++) _w[ei[notspecial[i]]] = 1;
int res = ask(_w);
if (res != A * pl) ans2 = x, low = x + 1;
else high = x - 1;
}
answer(special[ans1], notspecial[ans2]);
}
