#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define resetw w=vector<int>(m)
using pii=pair<int,int>;
const int lim=2e5;
int to[lim];
vector<int>v[lim],w;
int n,m,a,b;
pair<vector<int>,vector<vector<int>>>bfs(int st){
vector<int>dist(n,INT_MAX);
vector<vector<int>>pars(n);
queue<int>q;
dist[st]=0;
q.push(st);
while(q.size()){
int node=q.front();
q.pop();
for(int id:v[node]){
int j=to[id]^node;
if(w[id]){
continue;
}
if(dist[j]==INT_MAX){
q.push(j);
dist[j]=dist[node]+1;
}
if(dist[j]==dist[node]+1){
pars[j].pb(id);
}
}
}
return {dist,pars};
}
void find_pair(int N,vector<int>U,vector<int>V,int A,int B){
n=N;
m=V.size();
a=A;
b=B;
for(int i=0;i<m;i++){
v[U[i]].pb(i);
v[V[i]].pb(i);
to[i]=U[i]^V[i];
}
resetw;
int64_t none=ask(w);
int l=0,r=m-2,res=m-1;
while(l<=r){
int mid=l+r>>1;
resetw;
for(int i=0;i<=mid;i++){
w[i]=1;
}
int64_t cur=ask(w);
if(cur==none){
l=mid+1;
}else{
res=mid;
r=mid-1;
}
}
int guy=res;
int x=U[guy],y=V[guy];
vector<int>g1,g2;
resetw;
for(int i=0;i<=guy;i++){
w[i]=1;
}
auto[d1,p1]=bfs(x);
auto[d2,p2]=bfs(y);
for(int i=0;i<n;i++){
if(d1[i]<d2[i]){
g1.pb(i);
}else if(d2[i]<d1[i]){
g2.pb(i);
}
}
sort(g1.begin(),g1.end(),[&](int i,int j)-> bool {
return d1[j]<d1[i];
});
sort(g2.begin(),g2.end(),[&](int i,int j)-> bool {
return d2[j]<d2[i];
});
l=0,r=int(g1.size())-2,res=g1.size()-1;
while(l<=r){
int mid=l+r>>1;
resetw;
for(int i=0;i<guy;i++){
w[i]=1;
}
for(int i=0;i<=mid;i++){
for(int id:p1[g1[i]]){
w[id]=1;
}
}
int64_t cur=ask(w);
if(cur==none){
l=mid+1;
}else{
r=mid-1;
res=mid;
}
}
x=g1[res];
l=0,r=int(g2.size())-2,res=g2.size()-1;
while(l<=r){
int mid=l+r>>1;
resetw;
for(int i=0;i<guy;i++){
w[i]=1;
}
for(int i=0;i<=mid;i++){
for(int id:p2[g2[i]]){
w[id]=1;
}
}
int64_t cur=ask(w);
if(cur==none){
l=mid+1;
}else{
r=mid-1;
res=mid;
}
}
y=g2[res];
answer(x,y);
}
// void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
// int M = U.size();
// for (int j = 0; j < 50; ++j) {
// std::vector<int> w(M);
// for (int i = 0; i < M; ++i) {
// w[i] = 0;
// }
// long long toll = ask(w);
// }
// answer(0, N - 1);
// }
