#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>adj[100000];
void dfs(int u,vector<int>&x,vector<int>&nodes,int p,int val){
x.push_back(val);
nodes.push_back(u);
for(auto v:adj[u])if(v.first!=p)dfs(v.first,x,nodes,u,v.second);
}
void subtree(int n,vector<int>u,vector<int>v,int a,int b,long long cost){
//cerr<<"work\n";
int st=0,en=u.size()-1,ans=0;
while(st<=en){
int m=(st+en)/2;
//cerr<<"m:"<<m<<" ";
vector<int>temp;
for(int i=0;i<=m;i++)temp.push_back(1);
for(int i=m+1;i<n-1;i++)temp.push_back(0);
// cerr<<temp.size()<<"\n";
long long tcost=ask(temp);
//cerr<<tcost<<"\n";
if(tcost>cost){
en=m-1;
ans=m;
}else{
st=m+1;
}
}
int bg=u[ans];
int ed=v[ans];
//cerr<<bg<<" "<<ed<<"\n";
vector<int>temp;
vector<int>side1;
vector<int>side2;
vector<int>node1;
vector<int>node2;
for(int i=0;i<n-1;i++)temp.push_back(0);
dfs(bg,side1,node1,ed,ans);
dfs(ed,side2,node2,bg,ans);
for(auto x:side1)temp[x]=1;
long long cost1=ask(temp);
for(auto x:side1)temp[x]=0;
for(auto x:side2)temp[x]=1;
long long cost2=ask(temp);
for(int i=0;i<n-1;i++)temp[i]=0;
int n1,n2;
st=0,en=side1.size()-1;
for(int i=0;i<n-1;i++)temp[i]=0;
// cerr<<"side1\n";
//for(auto x:side1)cerr<<x<<" ";
// cerr<<"\n";
//cerr<<"side2\n";
//for(auto x:side2)cerr<<x<<" ";
//cerr<<"\n\n";
while(st<=en){
int m=(st+en)/2;
for(int i=0;i<=m;i++)temp[side1[i]]=1;
if(ask(temp)>=cost1){
en=m-1;
n1=m;
}else{
st=m+1;
}
for(int i=0;i<m;i++)temp[side1[i]]=0;
}
st=0,en=side2.size()-1;
while(st<=en){
int m=(st+en)/2;
for(int i=0;i<=m;i++)temp[side2[i]]=1;
if(ask(temp)>=cost2){
en=m-1;
n2=m;
}else{
st=m+1;
}
for(int i=0;i<m;i++)temp[side2[i]]=0;
}
//cerr<<node1[n1]<<" "<<node2[n2]<<"\n";
answer(node1[n1],node2[n2]);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
//cerr<<"work\n";
for(int i=0;i<U.size();i++){
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
vector<int>temp;
for(int i=0;i<N-1;i++)temp.push_back(0);
if(U.size()!=N-1)return answer(rand()%N,rand()%N);
else return subtree(N,U,V,A,B,ask(temp));
}
