#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include "highway.h"
using namespace std;
typedef long long LL;
typedef vector<int> Vi;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
#define forR(i, n) for (int i = 0; i < (n); i++)
#define MAXMN 130003
vector<vector<pair<int, int>>> nbs(MAXMN); // {nb, edgeNo}
vector<vector<pair<int, int>>> children(MAXMN);
vector<int> parent(MAXMN);
vector<int> parentEdge(MAXMN);
Vi edgeHeight(MAXMN);
int maxEdgeHeight = 0;
Vi edgeSorted;
int parentOf(int n1, int n2) {
if (parent[n1] == n2) return n2;
return n1;
}
int childOf(int n1, int n2) {
if (parent[n1] == n2) return n1;
return n2;
}
void build_tree(int root) {
Vb vis(MAXMN);
queue<pair<int, int>> q; q.push({ root, 0 }); // nodeNo, level
while (!q.empty()) {
auto p = q.front(); q.pop();
int x = p.first, level = p.second;
vis[x] = true;
for (auto nbP : nbs[x]) {
if (!vis[nbP.first]) {
q.push({ nbP.first, level + 1 });
children[x].push_back({ nbP.first, level + 1 });
parent[nbP.first] = x; parentEdge[nbP.first] = nbP.second;
edgeHeight[nbP.second] = level + 1;
maxEdgeHeight = max(maxEdgeHeight, level + 1);
edgeSorted.push_back(nbP.second);
}
}
}
}
void find_pair(int N, Vi U, Vi V, int A, int B) {
int m = U.size();
forR(i, m) {
nbs[U[i]].push_back({ V[i], i });
nbs[V[i]].push_back({ U[i], i });
}
build_tree(0);
LL dist = ask(Vi(m)) / A;
LL maxCost = dist * B;
// search for range of edges
int l = 0, r = m - 1;
while (l < r) {
int mid = (l + r) / 2;
Vi ws(m);
for (int i = mid + 1; i <= m - 1; i++) ws[edgeSorted[i]] = 1;
if (ask(ws) == maxCost) {
l = mid + 1;
} else {
r = mid;
}
}
int leftEdge = edgeSorted[l];
l = 0, r = m - 1;
while (l < r) {
int mid = (l + r) / 2;
Vi ws(m);
for (int i = 0; i <= mid; i++) ws[edgeSorted[i]] = 1;
if (ask(ws) == maxCost) {
r = mid;
} else {
l = mid + 1;
}
}
int rightEdge = edgeSorted[l];
int rootNode = parentOf(U[leftEdge], V[leftEdge]);
int rightChild = childOf(U[rightEdge], V[rightEdge]);
LL distR = 0; Vi REdges;
for (int n = rightChild; n != rootNode; n = parent[n]) {
REdges.push_back(parentEdge[n]);
distR++;
}
LL distL = dist - distR;
if (distL == 0) {
answer(rootNode, rightChild);
return;
}
LL maxCostL = distL * B + distR * A;
l = leftEdge, r = rightEdge;
while (l < r) {
int mid = (l + r) / 2;
Vi ws(m);
for (int i = l; i <= mid; i++) ws[edgeSorted[i]] = 1;
for (int e : REdges) ws[e] = 0;
if (ask(ws) == maxCostL) {
r = mid;
} else {
l = mid + 1;
}
}
int edgeLeft = edgeSorted[l];
int leftChild = childOf(U[edgeLeft], V[edgeLeft]);
answer(leftChild, rightChild);
}
