#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
vector<vector<pair<int, int>>> grafo;
vector<int> Marc;
// long long ask(vector<int> w);
int findNode(int S, vector<int> &w, int matters, ll dist)
{
queue<int> q; vector<int> poss;
Marc[S] = 1; q.push(S);
// w[matters] = 1;
while (!q.empty())
{
int cur = q.front(); q.pop();
poss.push_back(cur);
for (auto [viz, id] : grafo[cur])
{
if (Marc[viz] || w[id]) continue;
Marc[viz] = 1; q.push(viz);
}
}
// w[matters] = 0;
int id = 0;
for (int k = 16; k >= 0; k--)
{
int m = id | (1 << k);
if (m >= poss.size()) continue;
for (int v = 0; v < min(m, (int)poss.size()); v++)
for (auto [viz, id] : grafo[poss[v]])
w[id] = 0;
for (int v = m; v < poss.size(); v++)
for (auto [viz, id] : grafo[poss[v]])
w[id] = 1;
for (int i = matters+1; i < w.size(); i++) w[i] = 1;
if (ask(w) != dist) id |= (1 << k);
}
return poss[id];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
int M = U.size();
vector<int> w(M, 0);
ll dist = ask(w);
int matters = 0;
for (int k = 16; k >= 0; k--)
{
int m = matters | (1 << k);
if (m >= M) continue;
for (int i = 0; i < min(m, M); i++) w[i] = 0;
for (int i = m; i < M; i++) w[i] = 1;
if (ask(w) != dist) matters |= (1 << k);
}
for (int i = 0; i <= matters; i++) w[i] = 0;
for (int i = matters+1; i < M; i++) w[i] = 1;
grafo.resize(N); Marc.resize(N, 0);
for (int i = 0; i < M; i++)
{
grafo[U[i]].emplace_back(V[i], i);
grafo[V[i]].emplace_back(U[i], i);
}
// cerr << "matters: " << matters << ", (" << U[matters] << ", " << V[matters] << ") " << '\n';
int S = findNode(U[matters], w, matters, dist);
fill(Marc.begin(), Marc.end(), 0);
for (int i = 0; i <= matters; i++) w[i] = 0;
for (int i = matters+1; i < M; i++) w[i] = 1;
int T = findNode(S, w, matters, dist);
// cerr << "S: " << S << ", T: " << T << '\n';
answer(S, T);
}
