#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;
}
if (ask(w) == dist) {
pos = mid + 1;
l = mid + 1;
}
else {
r = mid - 1;
}
}
REP(i, pos) {
w[i] = 1;
}
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 (w[x.se] == 1) {
if (d[x.fi] == -1 || d[x.fi] > d[i] + costb) {
d[x.fi] = d[i] + costb;
dq.push_back(x.fi);
}
}
else {
if (d[x.fi] == -1 || d[x.fi] > d[i] + costa) {
d[x.fi] = d[i] + costa;
dq.push_front(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);
type[i] = 0;
}
else if (du[i] > dv[i]) {
verv.push_back(i);
type[i] = 1;
}
}
// for (auto x: veru) {
// cout << x << " ";
// }
// cout << "\n";
// for (auto x: verv) {
// cout << x << " ";
// }
// cout << "\n";
auto solve = [&] (const int &cur, 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);
REP(i, mid + 1) {
int j = vers[i];
// cout << j << " " << type[j] << "\n";
for (auto x: adj[j]) {
if (type[x.fi] != cur) {
continue;
}
if ((type[x.fi] == 0 && du[x.fi] < du[j]) || (type[x.fi] == 1 && dv[x.fi] < dv[j])) {
w[x.se] = 1;
// cout << "change " << x.se << "\n";
}
}
}
if (ask(w) == dist) {
pos = mid + 1;
l = mid + 1;
}
else {
r = mid - 1;
}
}
if (pos == sz(vers)) {
pos = 0;
}
// for (auto x: vers) {
// cout << x << " ";
// }
// cout << "-> " << vers[pos] << "\n";
return vers[pos];
};
answer(solve(0, veru), solve(1, verv));
}
