#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> bfs_order(int N, int M, int source, vector<int> U, vector<int> V) {
vector<int> edge[N];
for (int i = 0; i < M; i++) {
edge[U[i]].push_back(V[i]);
edge[V[i]].push_back(U[i]);
}
int cur = 0;
vector<int> ret(N, -1);
queue<int> bfs;
bfs.push(source);
while (!bfs.empty()) {
int u = bfs.front();
bfs.pop();
if (ret[u] > -1) continue;
ret[u] = cur++;
for (int v : edge[u])
bfs.push(v);
}
return ret;
}
int find_first(int N, int M, int source, ll targ, vector<int> U, vector<int> V) {
vector<int> ord = bfs_order(N, M, source, U, V);
int l = -1, r = N-1;
while (r-l > 1) {
int mid = (l+r)>>1;
vector<int> query(M, 1);
for (int i = 0; i < M; i++)
if (ord[U[i]] <= mid && ord[V[i]] <= mid)
query[i] = 0;
if (ask(query) > targ) l = mid;
else r = mid;
}
for (int i = 0; i < N; i++)
if (ord[i] == r)
return i;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
ll shortest_path = ask(vector<int>(M, 0));
// Find one node on the shortest path from S to T
int midnode = -1;
{
int l = -1, r = N-1;
while (r-l > 1) {
int mid = (l+r)>>1;
vector<int> query(M, 0);
for (int i = 0; i < M; i++)
if (U[i] <= mid || V[i] <= mid)
query[i] = 1;
if (ask(query) > shortest_path) r = mid;
else l = mid;
}
midnode = r;
}
int S = find_first(N, M, midnode, shortest_path, U, V);
int T = find_first(N, M, S, shortest_path, U, V);
answer(S, T);
}
