#include "highway.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = a; i < b; i++)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
pii solve(int N, std::vector<int> &U, std::vector<int> &V, int A, int B, vii &verts, vii &edges) {
int M = U.size();
vvpii adj(N);
forin(i, edges) {
adj[U[i]].emplace_back(V[i], i);
adj[V[i]].emplace_back(U[i], i);
}
vii depth(N, -1), parent(N), pedge(N);
depth[verts[0]] = 0;
function<void(int)> dfs;
dfs = [&](int x) {
forin(y, adj[x]) {
if (depth[y.first] == -1) {
depth[y.first] = depth[x] + 1;
parent[y.first] = x;
pedge[y.first] = y.second;
dfs(y.first);
}
}
};
dfs(verts[0]);
int deepest = verts[0];
forin(i, verts) {
if (depth[i] > depth[deepest]) {
deepest = i;
}
}
depth.assign(N, -1);
depth[deepest] = 0;
parent.assign(N, -1);
dfs(deepest);
int deepest2 = verts[0];
forin(i, verts) {
if (depth[i] > depth[deepest2]) {
deepest2 = i;
}
}
vii diameter = {deepest2}, dedges;
vii ondiam(N);
ondiam[deepest2] = 1;
while (diameter.back() != deepest) {
dedges.emplace_back(pedge[diameter.back()]);
diameter.emplace_back(parent[diameter.back()]);
ondiam[diameter.back()] = 1;
}
vii query(M);
ll dist = ask(query) / A;
forin(dedge, dedges) {
query[dedge] = 1;
}
ll ddist = (ask(query) - (dist * A)) / (B - A);
forin(dedge, dedges) {
query[dedge] = 0;
}
if (ddist == 0) {
deque<vii> groups(diameter.size()), groupse(diameter.size());
function<void(int, int)> dfs2;
dfs2 = [&](int x, int group) {
groups[group].emplace_back(x);
forin(y, adj[x]) {
if (y.first != parent[x]) {
if (ondiam[y.first]) {
dfs2(y.first, group + 1);
} else {
groupse[group].emplace_back(y.second);
dfs2(y.first, group);
}
}
}
};
dfs2(deepest, 0);
while (groups.size() > 1) {
vii query2(M);
rep(i, groups.size() / 2) {
forin(edge, groupse[i]) {
query2[edge] = 1;
}
}
if (ask(query2) > dist * A) {
groups.resize(groups.size() / 2);
groupse.resize(groupse.size() / 2);
} else {
int x = groups.size() - (groups.size() / 2);
rep(i, x) {
groups.pop_front();
groupse.pop_front();
}
}
}
auto &group = groups[0];
auto &groupe = groupse[0];
return solve(group.size(), U, V, A, B, group, groupe);
}
int lo = 0, hi = diameter.size() - 1 - ddist;
while (lo < hi) {
int mid = (lo + hi) / 2;
for (int x = mid; x >= 0; x-= ddist) {
query[dedges[x]] = 1;
}
if (ask(query) > dist * A) {
hi = mid;
} else {
lo = mid + 1;
}
for (int x = mid; x >= 0; x-= ddist) {
query[dedges[x]] = 0;
}
}
lo = diameter[lo];
hi = diameter[hi + ddist];
vii lodepth(N), hidepth(N);
int s, t;
deque<int> q = {lo};
while (!q.empty()) {
int x = q.front();
q.pop_front();
forin(y, adj[x]) {
if (y.first != parent[x] && !ondiam[y.first]) {
q.emplace_back(y.first);
query[y.second] = 1;
lodepth[y.first] = lodepth[x] + 1;
}
}
}
ll lodist = (ask(query) - (dist * A)) / (B - A);
query.assign(M, 0);
if (lodist == 0) {
s = lo;
} else {
vii cand;
rep(i, N) {
if (lodepth[i] == lodist) {
cand.emplace_back(i);
}
}
while (cand.size() > 1) {
vii query2(M);
rep(i, cand.size() / 2) {
query2[pedge[cand[i]]] = 1;
}
if (ask(query2) > dist * A) {
cand.resize(cand.size() / 2);
} else {
ffor(i, cand.size() / 2, cand.size()) {
cand[i - (cand.size() / 2)] = cand[i];
}
cand.resize(cand.size() - (cand.size() / 2));
}
}
s = cand[0];
}
q = {hi};
while (!q.empty()) {
int x = q.front();
q.pop_front();
forin(y, adj[x]) {
if (y.first != parent[x] && !ondiam[y.first]) {
q.emplace_back(y.first);
query[y.second] = 1;
hidepth[y.first] = hidepth[x] + 1;
}
}
}
ll hidist = (ask(query) - (dist * A)) / (B - A);
if (hidist == 0) {
t = hi;
} else {
vii cand;
rep(i, N) {
if (hidepth[i] == hidist) {
cand.emplace_back(i);
}
}
while (cand.size() > 1) {
vii query2(M);
rep(i, cand.size() / 2) {
query2[pedge[cand[i]]] = 1;
}
if (ask(query2) > dist * A) {
cand.resize(cand.size() / 2);
} else {
ffor(i, cand.size() / 2, cand.size()) {
cand[i - (cand.size() / 2)] = cand[i];
}
cand.resize(cand.size() - (cand.size() / 2));
}
}
t = cand[0];
}
return {s, t};
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
vii verts, edges;
rep(i, N) {
verts.emplace_back(i);
}
rep(i, U.size()) {
edges.emplace_back(i);
}
pii res = solve(N, U, V, A, B, verts, edges);
answer(res.first, res.second);
}
