#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mxn = 9e4 + 5;
vector<int> mn(mxn, 1e9), ord_id(mxn, 1e9);
vector<pii> g1[mxn], g[mxn];
void dfs(int u) {
for(auto [v, id] : g[u]) {
dfs(v);
mn[id] = ord_id[v];
ord_id[u] = min(ord_id[u], ord_id[v]);
}
}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
ll len = 0, m = U.size();
vector<int> dummy(m);
len = ask(dummy) / A;
queue<int> q;
for(int i=0; i<m; i++) {
g1[U[i]].push_back({ V[i], i });
g1[V[i]].push_back({ U[i], i });
}
q.push(0);
vector<int> dist(n, -1), ord;
dist[0] = 0;
int curr = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
if(dist[u] == len) {
ord_id[u] = curr++;
ord.push_back(u);
continue;
}
for(auto [v, id] : g1[u]) {
if(dist[v] != -1) continue;
dist[v] = dist[u] + 1;
q.push(v);
g[u].push_back({ v, id });
}
}
dfs(0);
int l=0, r=ord.size()-1, p=0;
while(l <= r) {
int mid = (l + r) / 2;
vector<int> to_get(m, 1);
for(int i=0; i<m; i++)
if(mn[i] <= mid) to_get[i] = 0;
ll res = ask(to_get);
if(res == (ll)len * A) p = mid, r = mid - 1;
else l = mid + 1;
}
answer(0, ord[p]);
}
