#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010, inf = 1e9;
#include "highway.h"
int n, m;
vector<int> edge[MAX_N];
vector<pair<int,int>> alle;
ll A, B, edis, rdis;
// node is banned
ll qry(vector<int> ban_list) {
debug(AI(ban_list));
vector<int> ban(n);
for (int u : ban_list) ban[u] = true;
vector<int> w(m);
for (int i = 0;i < m;++i) {
auto [x, y] = alle[i];
w[i] = ban[x] || ban[y];
}
return ask(w);
}
// edge is banned
ll qry(vector<pair<int,int>> ban_list) {
sort(AI(ban_list));
vector<int> w(m);
for (int i = 0;i < m;++i) {
auto [x, y] = alle[i];
if (binary_search(AI(ban_list), make_pair(x, y)) ||
binary_search(AI(ban_list), make_pair(y, x)))
w[i] = true;
}
return ask(w);
}
int find_on_path() {
auto gen_vec = [&](int id) {
vector<int> a;
for (int i = 0;i <= id;++i) a.pb(i);
return a;
};
int l = 0, r = n-1, mid;
while (l < r) {
mid = l + r >> 1;
if (qry(gen_vec(mid)) == rdis)
l = mid+1;
else
r = mid;
}
return l;
}
vector<int> lev[MAX_N];
int search_dis(int f) {
vector<int> dis(n, inf);
dis[f] = 0;
queue<int> q;
q.emplace(f);
while (q.size()) {
int x = q.front(); q.pop();
lev[ dis[x] ].pb(x);
for (int u : edge[x]) if (chmin(dis[u], dis[x] + 1))
q.emplace(u);
}
int l = 1, r = n-1, mid;
auto gen_vec = [&](int d) {
vector<int> all;
for (int i = 0;i < n;++i) if (dis[i] <= d)
all.pb(i);
return all;
};
while (l < r) {
mid = l + r >> 1;
ll qv = qry(gen_vec(mid));
if (qv == B * edis)
r = mid;
else
l = mid+1;
}
return l;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
::A = A, ::B = B;
n = N, m = U.size();
for (int i = 0;i < m;++i) {
alle.pb(U[i], V[i]);
edge[U[i]].pb(V[i]);
edge[V[i]].pb(U[i]);
}
rdis = qry( vector<int>{} );
edis = rdis / A;
int f = find_on_path();
int a = search_dis(f), b = edis - a;
vector<int> res;
function<void(vector<int>,int)> bins = [&](vector<int> cand, int sum) {
if (sum == 0) return;
if (cand.size() == 1) {
res.pb(cand[0]);
return;
}
int mid = cand.size() / 2;
vector<int> l, r;
for (int i = 0;i < cand.size();++i)
(i<=mid?l:r).pb(cand[i]);
ll v = qry(l);
int lsum = 0, rsum = 0;
if (sum == 2) {
ll u = qry(r);
if (v > rdis) lsum = 1;
if (u > rdis) rsum = 1;
if (v == rdis) rsum = 2;
if (u == rdis) lsum = 2;
}
else {
if (v > rdis) lsum = 1;
else rsum = 1;
}
bins(l, lsum), bins(r, rsum);
};
if (a == b) {
bins(lev[a], 2);
}
else {
bins(lev[a], 1), bins(lev[b], 1);
}
answer(res[0], res[1]);
}
