#include "highway.h"
#include <bits/stdc++.h>
using i64 = long long;
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
const int M = (int)U.size();
std::vector<std::vector<std::pair<int, int>>> graph(N);
for (int i = 0; i < M; ++i) {
graph[U[i]].push_back({V[i], i});
graph[V[i]].push_back({U[i], i});
}
// find one of the vertices on the min cost path
const int distLen = ask(std::vector<int>(M, 0)) / A;
auto binarySearch = [&](int ng, int ok, auto &&f) {
while (std::abs(ok - ng) > 1) {
const auto mid = (ok + ng) / 2;
if (f(mid)) ok = mid;
else ng = mid;
}
return ok;
};
int root = binarySearch(0, N, [&](const int m) {
std::vector<int> w(M);
for (int i = 0; i < M; ++i) {
const int mx = std::max(U[i], V[i]);
w[i] = mx < m ? 0 : 1;
}
return ask(w) == (i64)(distLen) * A;
}) - 1;
// construct BFS-Tree
std::vector<std::vector<std::pair<int, int>>> bfsTree(N);
std::vector<int> parent(N, -1);
std::queue<int> que;
que.push(root);
std::vector<bool> isSeen(N);
isSeen[root] = true;
std::vector<bool> exTree(M);
while (not que.empty()) {
const int f = que.front();
que.pop();
for (const auto &[t, i] : graph[f]) {
if (isSeen[t]) continue;
isSeen[t] = true;
bfsTree[f].push_back({t, i});
exTree[i] = true;
parent[t] = f;
que.push(t);
}
}
// Euler-Tour
std::vector<int> in(N, -1), revIn(N);
auto dfs = [&](auto &&self, const int v, int &id) -> void {
revIn[id] = v;
in[v] = id;
++id;
for (const auto &[t, i] : bfsTree[v]) {
if (in[t] != -1) continue;
self(self, t, id);
}
};
int gomi = 0;
dfs(dfs, root, gomi);
// binary search, find path
// find r
int r = binarySearch(0, N, [&](const int m) {
std::vector<int> w(M);
for (int i = 0; i < M; ++i) {
if (not exTree[i]) continue;
const int mx = std::max(in[U[i]], in[V[i]]);
w[i] = mx < m ? 0 : 1;
}
return ask(w) == (i64)(distLen) * A;
}) - 1;
int r2 = revIn[r];
while (parent[r2] != -1 and in[parent[r2]] != 0) {
r2 = parent[r2];
}
r2 = in[r2];
int l = binarySearch(0, r2, [&](const int m) {
std::vector<int> w(M);
for (int i = 0; i < M; ++i) {
if (not exTree[i]) continue;
const int mx = std::max(in[U[i]], in[V[i]]);
if (mx >= r2) w[i] = 0;
else w[i] = mx < m ? 0 : 1;
}
return ask(w) == (i64)(distLen) * A;
}) - 1;
answer(revIn[l], revIn[r]);
}
