#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int MAX_N = 9e4 + 5;
vector<vector<pair<int, int>>> g(MAX_N);
vector<int> up(MAX_N);
vector<pair<int, int>> dist;
vector<vector<pair<int, int>>> h(MAX_N);
int Time = 0;
vector<int> in(MAX_N), out(MAX_N);
int _A, _B, max_h = 0;
void calc(int node, int p, int height, int where) {
in[node] = ++Time;
max_h = max(max_h, height);
up[node] = where;
h[height].emplace_back(up[node], node);
for (auto to : g[node]) {
if (to.first != p) {
calc(to.first, node, height + 1, to.second);
}
}
out[node] = Time;
}
int st;
bool in_sub(int u, int v) {
return in[u] <= in[v] && out[u] >= out[v];
}
void dfs(int node, int p, i64 goal_distance, i64 w) {
if (w == goal_distance) {
if (in_sub(node, st) == false) {
dist.emplace_back(up[node], node);
} else {
for (auto to : g[node]) {
if (in[to.first] < in[node]) continue;
if (in_sub(to.first, st) == true) {
dist.emplace_back(to.second, node);
break;
}
}
}
}
for (auto to : g[node]) {
if (to.first != p) {
dfs(to.first, node, goal_distance, w + _A);
}
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
_A = A;
_B = B;
const int m = (int) U.size();
for (int i = 0; i < m; i++) {
const int u = U[i];
const int v = V[i];
g[u].emplace_back(v, i);
g[v].emplace_back(u, i);
}
calc(0, -1, 0, -1);
vector<int> q(m);
const i64 shortest_path = ask(q);
int lo = 1, hi = max_h + 1;
while(lo < hi) {
const int mid = lo + (hi - lo) / 2;
q.clear();
q.resize(m);
for (int i = max_h; i >= mid; i--) {
for (auto to : h[i]) {
q[to.first] = 1;
}
}
i64 new_shortest = ask(q);
if (new_shortest == shortest_path) {
hi = mid;
} else {
lo = mid + 1;
}
}
--hi;
const int lowest = hi;
assert(hi > 0);
lo = 0;
hi = h[hi].size();
while(lo < hi) {
const int mid = lo + (hi - lo) / 2;
q.clear();
q.resize(m);
for (int i = 0; i <= mid; i++) {
q[h[lowest][i].first] = 1;
}
i64 new_shortest = ask(q);
if (new_shortest > shortest_path) {
hi = mid;
} else {
lo = mid + 1;
}
}
st = h[lowest][hi].second;
dfs(st, -1, shortest_path, 0);
lo = 0;
hi = (int) dist.size();
while(lo < hi) {
const int mid = lo + (hi - lo) / 2;
q.clear();
q.resize(m);
for (int i = 0; i <= mid; i++) {
const int edge = dist[i].first;
q[edge] = 1;
}
i64 new_shortest = ask(q);
if (new_shortest > shortest_path) {
hi = mid;
} else {
lo = mid + 1;
}
}
answer(st, dist[hi].second);
}
