#include "highway.h"
#include "bits/stdc++.h"
using namespace std;
long long n, m, a, b;
vector< vector<long long> > Grafo;
vector<int> Consulta;
vector<long long> Anteriores, Distancias;
map< pair<long long, long long>, long long> Identificador;
void DFS(long long Nodo, long long Anterior){
Anteriores[Nodo] = Anterior;
Distancias[Nodo] = Distancias[Anterior] + 1;
for(auto E: Grafo[Nodo]){
if(E == Anterior) continue;
DFS(E, Nodo);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
n = N, m = U.size(), a = A, b = B;
Grafo.assign(n, {});
Anteriores.assign(n, 0);
Distancias.assign(n, -1);
Consulta.assign(m, 0);
long long Distancia = ask(Consulta) / a;
long long j = 0;
for(long long i = 0; i < m; i++){
Grafo[U[i]].push_back(V[i]);
Grafo[V[i]].push_back(U[i]);
Identificador[{U[i], V[i]}] = j;
Identificador[{V[i], U[i]}] = j;
j++;
}
DFS(0, 0);
vector<bool> Sirven(n, 0);
for(long long i = 0; i < n; i++){
if(Distancias[i] == Distancia) Sirven[i] = 1;
}
while(2 == 2){
long long c = 0, r;
for(long long i = 0; i < n; i++){
if(Sirven[i]){
c++;
r = i;
}
}
if(c == 1){
answer(0, r);
return;
}
c /= 2;
long long cc = c;
Consulta = vector<int>(m, 0);
long long Continuar = 0;
for(long long i = 0; i < n and cc > 0; i++){
if(Sirven[i]){
cc--;
Consulta[Identificador[{i, Anteriores[i]}]] = 1;
Continuar = i + 1;
}
}
if(ask(Consulta) == Distancia * a){
for(long long i = 0; i < n and c > 0; i++){
if(Sirven[i]){
c--;
Sirven[i] = 0;
}
}
} else {
for(; Continuar < n; Continuar++){
if(Sirven[Continuar]){
Sirven[Continuar] = 0;
}
}
}
}
}
