#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int MAX=2e5+5;
const int INF=1<<30;
int M;
vector<int> qry;
vector<pii> adj[MAX];
vector<int> spt;
int dst[MAX];
vector<pii> adj0[MAX];
vector<pii> ord;
void dfs(int x,int p){
for (auto [y,ei]:adj0[x]) if (y!=p) dfs(y,x),ord.push_back({y,ei});
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
M=U.size();
qry.resize(M);
fill(qry.begin(),qry.end(),0);
for (int i=0;i<M;i++){
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
ll t=ask(qry);
int l=0,r=M-1;
while (l!=r){
int m=(l+r)/2;
for (int i=0;i<=m;i++) qry[i]=1;
for (int i=m+1;i<M;i++) qry[i]=0;
if (ask(qry)!=t) r=m;
else l=m+1;
}
priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<>> pq; // {d,{ei,i}}
int rt0=U[l],rt1=V[l];
fill_n(dst,N,INF);
pq.push({0,{-1,rt0}});
while (pq.size()){
auto [d,pr]=pq.top();
auto [ei,x]=pr;
pq.pop();
if (d>=dst[x]) continue;
dst[x]=d;
if (ei!=-1) spt.push_back(ei);
for (auto [y,ej]:adj[x]) pq.push({d+1,{ej,y}});
}
for (auto ei:spt){
adj0[U[ei]].push_back({V[ei],ei});
adj0[V[ei]].push_back({U[ei],ei});
}
fill(qry.begin(),qry.end(),1);
for (auto ei:spt) qry[ei]=0;
dfs(rt0,rt1);
ord.push_back({rt0,-1});
l=0;r=ord.size()-1;
while (l!=r){
int m=(l+r)/2;
for (int i=0;i<=m;i++) qry[ord[i].second]=1;
for (int i=m+1;i<ord.size()-1;i++) qry[ord[i].second]=0;
if (ask(qry)!=t) r=m;
else l=m+1;
}
int S=ord[l].first;
for (auto ei:spt) qry[ei]=0;
ord.clear();
dfs(rt1,rt0);
ord.push_back({rt1,-1});
l=0;r=ord.size()-1;
while (l!=r){
int m=(l+r)/2;
for (int i=0;i<=m;i++) qry[ord[i].second]=1;
for (int i=m+1;i<ord.size()-1;i++) qry[ord[i].second]=0;
if (ask(qry)!=t) r=m;
else l=m+1;
}
int E=ord[l].first;
answer(S,E);
}
