#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
struct edge{
int to,id;
};
vector<edge>V[900000];
int dist[900000];
void dfs(int x,int from){
for(edge e:V[x]){
if(e.to==from)continue;
dist[e.to]=dist[x]+1;
dfs(e.to,x);
}
}
void find_pair(int N,vector<int>u,vector<int>v,int A,int B){
for(int i=0;i<N;i++){
V[i].clear();
}
int M=u.size();
assert(M==N-1);
for(int i=0;i<M;i++){
V[u[i]].push_back({v[i],i});
V[v[i]].push_back({u[i],i});
}
long long Base=ask(vector<int>(M,0));
int path_len=Base/A;
int l,r;
l=-1;
r=M-1;
while(l+1!=r){
int m=(l+r)/2;
vector<int>K(M,0);
for(int i=0;i<=m;i++){
K[i]=1;
}
int t=ask(K);
if(t>Base){
r=m;
}
else{
l=m;
}
}
int p=u[r];
int q=v[r];
vector<int>K(M,0);
K[r]=1;
queue<int>que;
que.push(q);
while(!que.empty()){
int x=que.front();
que.pop();
for(edge e:V[x]){
if(K[e.id])continue;
K[e.id]=true;
que.push(e.to);
}
}
K[r]=0;
long long t=ask(K);
int len=(t-Base)/(B-A);
int S,T;
for(int i=0;i<N;i++){
dist[i]=-1;
}
dist[q]=0;
dfs(q,p);
vector<int>W;
for(int i=0;i<N;i++){
if(dist[i]==len){
W.push_back(i);
}
}
l=-1;
r=W.size()-1;
while(l+1!=r){
int m=(l+r)/2;
vector<int>K(M,0);
for(int i=0;i<=m;i++){
for(edge e:V[W[i]]){
K[e.id]=1;
}
}
if(Base!=ask(K)){
r=m;
}
else{
l=m;
}
}
S=W[r];
W.clear();
for(int i=0;i<N;i++){
dist[i]=-1;
}
dist[p]=0;
dfs(p,q);
for(int i=0;i<N;i++){
if(dist[i]==path_len-1-len){
W.push_back(i);
}
}
l=-1;
r=W.size()-1;
while(l+1!=r){
int m=(l+r)/2;
vector<int>K(M,0);
for(int i=0;i<=m;i++){
for(edge e:V[W[i]]){
K[e.id]=1;
}
}
if(Base!=ask(K)){
r=m;
}
else{
l=m;
}
}
T=W[r];
answer(S,T);
}
