#include "highway.h"
using namespace std;
#define ALL(x) begin(x),end(x)
#define pb push_back
#define F first
#define S second
// #define int long long
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vb> vvb;
template<typename T>
T meq(T& a, T b){
return a=max(a,b);
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
int m = U.size();
vvii g(n);
for (int i=0;i<m;i++){
g[U[i]].pb({V[i],i});
g[V[i]].pb({U[i],i});
}
vi w(m, 0);
ll dist = ask(w);
vi dep(n,-1);
vi depe(m,-1);
vi pare(n,-1);
auto dfs1 = [&](auto&& self, int i, int d) -> void {
if (dep[i]!=-1)return;
dep[i] = d;
for (auto [j,eg]:g[i]){
if (dep[j]!=-1)continue;;
depe[eg]=d+1;
pare[j]=eg;
self(self, j, d+1);
}
};
dfs1(dfs1, 0, 0);
int dl=0,dr=0;
for (int d:dep)meq(dr, d+1);
while (dl<dr-1){
int md=(dl+dr)/2;
for (int i=0;i<m;i++)w[i]=depe[i]>=md;
if (ask(w)>dist)dl=md;
else dr=md;
}
vii poss;
for (int i=0;i<n;i++){
if (dep[i]==dl)poss.pb({i,pare[i]});
}
while (poss.size()>1){
vii test;
fill(ALL(w),0);
while (test.size()<poss.size()){
test.pb(poss.back());
w[poss.back().S]=1;
poss.pop_back();
}
if (ask(w)>dist){
swap(test,poss);
}
}
const int ans1 = poss[0].F;
fill(ALL(dep),-1);
vii poss2;
auto dfs2 = [&](auto&& self, int i, int d) -> void {
if (dep[i]!=-1)return;
dep[i] = d;
for (auto [j,eg]:g[i]){
if (dep[j]!=-1)continue;
if (d+1==dist/A){
poss2.pb({j,eg});
}
self(self, j, d+1);
}
};
dfs2(dfs2, ans1, 0);
while (poss2.size()>1){
vii test;
fill(ALL(w),0);
while (test.size()<poss2.size()){
test.pb(poss2.back());
w[poss2.back().S]=1;
poss2.pop_back();
}
if (ask(w)>dist){
swap(test,poss2);
}
}
const int ans2 = poss2[0].F;
answer(ans1, ans2);
}
