#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
const int maxn = (int)1e5;
vector<vector<pair<int, int>>> g;
vector<int> ose, el, gTav;
long long tav, A, B;
int N, M;
int el_keres(){
vector<int> query(M, 0);
int l = 0, r = M;
while(l+1 < r){
vector<int> query2 = query;
int m = (l+r)/2;
for(int i = l; i < m; i++)
query2[i] = 1;
long long ans = ask(query2);
if(ans != tav*A){
r = m;
} else{
for(int i = l; i < m; i++)
query[i] = 1;
l = m;
}
}
return l;
}
int sor[maxn];
void bejar(int x, int y, int elInd){
vector<bool> volt(N, false);
sor[0] = x;
sor[1] = y;
volt[x] = volt[y] = true;
ose[x] = x;
ose[y] = y;
el[x] = el[y] = elInd;
gTav[x] = gTav[y] = 0;
int ind = 0, veg = 2;
while(ind < veg){
int akt = sor[ind];
for(auto e : g[akt]){
if(!volt[e.first]){
volt[e.first] = true;
el[e.first] = e.second;
ose[e.first] = ose[akt];
gTav[e.first] = gTav[akt]+1;
sor[veg++] = e.first;
}
}
ind++;
}
}
int get(int os){
vector<int> v;
for(int i = 0; i < N; i++)
if(ose[i] == os)
v.push_back(i);
sort(v.begin(), v.end(), [](int a, int b){return gTav[a] < gTav[b]; });
int l = 0, r = (int)v.size();
while(l+1 < r){
int m = (l+r)/2;
vector<int> query(M, 1);
for(int i = m; i < r; i++)
query[el[v[i]]] = 0;
long long ans = ask(query);
if(ans < tav*B)
l = m;
else
r = m;
}
return v[l];
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int CA, int CB) {
//cout<<"called"<<endl;
N = n;
M = (int)U.size();
A = CA;
B = CB;
g.resize(N);
el.resize(N);
ose.resize(N);
gTav.resize(N);
for(int i = 0; i < M; i++){
g[U[i]].emplace_back(V[i], i);
g[V[i]].emplace_back(U[i], i);
}
vector<int> query(M, 0);
tav = ask(query)/A;
//cout<<"tav: "<<tav<<endl;
int ind = el_keres();
//cout<<"keres kesz | ind: "<<ind<<endl;
bejar(U[ind], V[ind], ind);
//cout<<"bejar kesz"<<endl;
answer(get(U[ind]), get(V[ind]));
}
