#include<bits/stdc++.h>
#include "diameter.h"
using namespace std;
int cal(int x,int y){
int d=1e9;
int _=0;
for(int i=1;i<=n;i++){
if(i==x||i==y)continue;
int dd=query(x,y,i);
if(dd<d){
d=dd;
_=i;
}
}
if(!in(_,x,y))d=1;
while(d>1){
for(int i=1;i<=n;i++){
if(i==x||i==y)continue;
int dd=query(x,y,i);
if(dd<=d){
d=dd;
y=i;
break;
}
}
}
int mx=0;
int u=y;
for(int i=1;i<=n;i++){
if(i==x||i==y)continue;
int dd=query(i,x,y);
if(dd>mx){
mx=dd;
u=i;
}
}
return u;
}
std::pair<int, int> find_diameter(int subid, int n) {
if(n==1)return make_pair(1,1);
if(n==2)return make_pair(1,2);
int u=cal(1,2);
int v=cal(u,2);
return make_pair(u,v);
}