#include "highway.h"
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
#define PAIR(i,j) pair<i, j>
vector<vector<pair<int, int> > > graph;
vector<vector<int> > spreadTree;
vector<int> last;
void addLayer2SpreadTree(int value, int i) {
spreadTree[i].push_back(value);
// for auto i: l {
//
// }
}
std::vector<int> UU;
std::vector<int> VV;
int MM;
long long total0;
void doSpread(int from, long long maxStep) {
spreadTree.clear();
last.clear();
last.resize(MM);
bool visisted[MM];
fill(visisted, visisted + MM, false);
// spread from 0
queue<pair<int, int> > q;
q.push(make_pair(from, 0));
visisted[from] = true;
last[from] = UU[from];
while (!q.empty()) {
pair<int, int> v = q.front();
q.pop();
if (v.second > maxStep) {
break;
}
if (v.second >= spreadTree.size()) {
spreadTree.push_back(vector<int>());
}
spreadTree[v.second].push_back(v.first);
vector<pair<int, int> > join = graph[UU[v.first]];
join.insert(join.end(), graph[VV[v.first]].begin(), graph[VV[v.first]].end());
for (auto e : join) {
if (!visisted[e.second]) {
visisted[e.second] = true;
last[e.second] = e.first;
q.push(make_pair(e.second, v.second + 1));
}
}
}
}
int binarySearch() {
int left = 0, right = spreadTree.size() - 1;
std::vector<int> w(MM);
fill(w.begin(), w.end(), 0);
while (left < right) {
int mid = left + (right - left) / 2;
int k = 0;
for (int i = left; i <= right; ++i) {
if (i > mid) {
k = 1;
}
for (auto j: spreadTree[i]) {
w[j] = k;
}
}
long long toll = ask(w);
if (total0 != toll) {
left = mid + 1;
} else {
right = mid;
}
}
fill(w.begin(), w.end(), 0);
int step = left;
left = 0; right = spreadTree[step].size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
int k = 0;
for (int i = left; i <= right; ++i) {
if (i > mid) {
k = 1;
}
w[spreadTree[step][i]] = k;
}
long long toll = ask(w);
if (total0 != toll) {
left = mid + 1;
} else {
right = mid;
}
}
return spreadTree[step][left];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
UU = U; VV = V;
MM = M;
graph.resize(N);
for (int i = 0; i < M; ++i) {
graph[U[i]].push_back(make_pair(V[i], i));
graph[V[i]].push_back(make_pair(U[i], i));
}
std::vector<int> w(MM);
for (int i = 0; i < MM; ++i) {
w[i] = 0;
}
total0 = ask(w);
// spread from 0
doSpread(0, M);
int s, t;
long long maxStep = total0 / A;
// binary search
int midEdge = binarySearch();
// spread to max
doSpread(midEdge, maxStep);
int lastPoint = binarySearch();
s = last[lastPoint];
doSpread(lastPoint, maxStep);
int secondPoint = binarySearch();
t = last[secondPoint];
answer(s, t);
}
