#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<ll,ll>>> graph;
vector<ll> dist;
vector<pair<ll,ll>> padre;
void dfs(ll now,ll ante){
for(auto u:graph[now]){
if(u.first==ante){
continue;
}
padre[u.first].first=now;
padre[u.first].second=u.second;
dist[u.first]=dist[now]+1;
dfs(u.first,now);
}
}
void find_pair(int N,vector<int> U,vector<int> V, int A, int B){
graph.clear();
graph.resize(N);
dist.assign(N,0);
padre.assign(N,{0,0});
ll M=U.size();
for(ll i=0;i<M;i++){
graph[U[i]].push_back({V[i],i});
graph[V[i]].push_back({U[i],i});
}
dfs(0,-1);
vector<int> aske(M,0);
vector<int> second;
ll res=ask(aske);
ll nue=0,con=0,con1=0;
for(ll i=1;i<N;i++){
if(dist[i]*A==res){
aske[padre[i].second]=1;
con++;
}
}
res+=-A+B;
while(con>1){
second=aske;
con1=con;
for(int i=0;i<M;i++){
if(second[i] && con1>(con/2)){
second[i]=0;
con1--;
}
}
nue=ask(second);
if(nue==res){
res=nue;
aske=second;
con=con1;
}else{
for(int i=0;i<M;i++){
if(second[i]){
aske[i]=0;
}
}
con-=con1;
}
}
for(int i=0;i<M;i++){
if(aske[i]){
for(int j=0;j<N;j++){
if(padre[j].second==i){
answer(0,j);
return;
}
}
}
}
}
