#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int N, M, A, B;
vector<signed> U, V;
const int MAXN = 90000;
const int MAXM = 130000;
int queriesSoFar = 0;
long long allLightCost;
vector<pair<int,int>> AdjList[90005];
bitset<MAXN> nodesToCheck;
vector<signed> edgesToCheck;
long long checkNodes() {
edgesToCheck.assign(M,0);
for(int v = 0; v < N; v++) {
if(!nodesToCheck[v])
continue;
for(auto p: AdjList[v])
edgesToCheck[p.second]=1;
}
queriesSoFar++;
return ask(edgesToCheck);
}
void find_pair(signed N_, vector<signed> U_, vector<signed> V_, signed A_, signed B_) {
N=N_; U=U_;V=V_;A=A_;B=B_;
M = U.size();
edgesToCheck.assign(M, 0);
srand(time(NULL));
for(int e = 0; e < M; e++) {
AdjList[U[e]].push_back({V[e],e});
AdjList[V[e]].push_back({U[e],e});
}
allLightCost = checkNodes();
//-----------Get Edge In Path-------------//
vector<int> randomisedNodes(N);
for(int i = 0; i < N; i++)
randomisedNodes[i]=i;
random_shuffle(randomisedNodes.begin(), randomisedNodes.end());
int lo = 0;
int hi = N;
while(lo+1 < hi) {
int mid = (lo+hi)/2;
nodesToCheck.reset();
for(int i = 0; i < mid; i++)
nodesToCheck[randomisedNodes[i]]=1;
long long cur = checkNodes();
if(cur > allLightCost) hi = mid;
else lo = mid;
}
int onPath = randomisedNodes[lo];
//-----------Get Edge In Path-------------//
//------------Get Nearer End--------------//
vector<int> dist(N,N+10);
dist[onPath] = 0;
queue<pair<int,int>> q;
q.push({onPath, 0});
while(!q.empty()) {
int u = q.front().first;
int d = q.front().second;
q.pop();
for(auto p: AdjList[u]) {
int v = p.first;
if(dist[v] > d+1) {
dist[v] = d+1;
q.push({v,d+1});
}
}
}
int diff = allLightCost/A;
lo = 0;
hi = (diff/2)+1;
while(lo+1 < hi) {
int mid = (lo+hi)/2;
nodesToCheck.reset();
for(int i = 0; i < N; i++)
if(dist[i] < mid)
nodesToCheck[i] = 1;
long long expected = allLightCost - (mid)*2*A + (mid)*2*B;
long long act = checkNodes();
if(expected == act) lo = mid;
else hi = mid;
}
int distToNearest = lo;
//------------Get Nearer End--------------//
//------------Get Closer Node-------------//
vector<int> possibilites;
for(int i = 0; i < N; i++)
if(dist[i] == distToNearest)
possibilites.push_back(i);
random_shuffle(possibilites.begin(), possibilites.end());
lo = 0;
hi = possibilites.size();
while(lo+1 < hi) {
int mid = (lo+hi)/2;
nodesToCheck.reset();
for(int i = 0; i < mid; i++)
nodesToCheck[possibilites[i]]=1;
long long cur = checkNodes();
if(cur == allLightCost)
lo = mid;
else if(cur == allLightCost + (B-A) + (B-A) + (B-A))
hi = mid;
else if(cur == allLightCost + (B-A))
hi = mid;
else {
if(distToNearest*2 == diff)
hi = mid;
else
lo = mid;
}
}
int S = possibilites[lo];
//------------Get Closer Node-------------//
//------------Get Further Node------------//
possibilites.clear();
int distToFurther = diff - distToNearest;
for(int i = 0; i < N; i++)
if(dist[i] == distToFurther && i != S)
possibilites.push_back(i);
random_shuffle(possibilites.begin(), possibilites.end());
lo = 0;
hi = possibilites.size();
while(lo+1 < hi) {
int mid = (lo+hi)/2;
nodesToCheck.reset();
for(int i = 0; i < mid; i++)
nodesToCheck[possibilites[i]]=1;
long long cur = checkNodes();
if(cur == allLightCost)
lo = mid;
else
hi = mid;
}
int T = possibilites[lo];
//------------Get Further Node------------//
answer(S,T);
}
