#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define NAME ""
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())
const int nmax = 9e4;
vector < pii > adj[nmax + 4];
void find_pair(int n, std::vector<int> u, std::vector<int> v, int costa, int costb) {
int m = sz(u);
REP(i, m) {
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
}
vector < int > w(m, 0);
ll dist = ask(w);
int l = 0, r = m - 1, pos = 0;
while (l <= r) {
int mid = (l + r) >> 1;
REP(i, mid + 1) {
w[i] = 1;
}
// cout << ask(w) << " " << dist << " " << mid << "\n";
if (ask(w) != dist) {
pos = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
REP(i, mid + 1) {
w[i] = 0;
}
}
// cout << pos << "\n";
auto bfs = [&] (const int &i) {
vector < int > d(n, -1);
d[i] = 0;
deque < int > dq;
int timer = 0;
dq.push_back(i);
while (!dq.empty()) {
int i = dq.front();
dq.pop_front();
for (auto x: adj[i]) {
if (d[x.fi] == -1) {
d[x.fi] = d[i] + 1;
dq.push_back(x.fi);
}
}
}
return move(d);
};
vector < int > du = bfs(u[pos]);
vector < int > dv = bfs(v[pos]);
vector < int > veru, verv, type(n, -1);
REP(i, n) {
if (du[i] < dv[i]) {
veru.push_back(i);
}
else if (du[i] > dv[i]) {
verv.push_back(i);
}
}
sort(veru.begin(), veru.end(), [&] (const int &x, const int &y) {
return (du[x] < du[y]);
});
sort(verv.begin(), verv.end(), [&] (const int &x, const int &y) {
return (dv[x] < dv[y]);
});
// for (auto x: veru) {
// cout << x << " ";
// }
// cout << "\n";
// for (auto x: verv) {
// cout << x << " ";
// }
// cout << "\n";
auto solve = [&] (const vector < int > & vers) {
int l = 0, r = sz(vers) - 1, pos = 0;
while (l <= r) {
int mid = (l + r) >> 1;
vector < int > w(m, 0);
FOR(i, mid + 1, sz(vers) - 1) {
int j = vers[i];
// cout << j << " " << type[j] << "\n";
for (auto x: adj[j]) {
w[x.se] = 1;
}
}
if (ask(w) == dist) {
pos = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
// for (auto x: vers) {
// cout << x << " ";
// }
// cout << "-> " << vers[pos] << "\n";
return vers[pos];
};
answer(solve(veru), solve(verv));
}
