#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;
int _A, _B;
void calc(int node, int p, int where) {
up[node] = where;
for (auto to : g[node]) {
if (to.first != p) {
calc(to.first, node, to.second);
}
}
}
void dfs(int node, int p, i64 goal_distance, i64 w) {
if (w == goal_distance) {
dist.emplace_back(up[node], node);
}
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 st = 0;
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, -1);
vector<int> q(m);
const i64 shortest_path = ask(q);
dfs(0, -1, shortest_path, 0);
// Assuming one node is 0
int 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);
}
