// 위대한 - 주의 만세!
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include"diameter.h"
#define fi first
#define se second
#define mkp std::make_pair
using llu=long long unsigned;
using ll=long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}
auto find_diameter(int sid,int N){
if(N==1) return mkp(1,1);
if(N==2) return mkp(1,2);
if(N==3){
return in(1,2,3)?mkp(2,3):(in(2,1,3)?mkp(1,3):mkp(1,2));
}
int x=1,y=2,z=0,t=0;
std::vector<int> a(N+1,0);
int mx=0;
for(int i=1;i<=N;++i) if(i!=x&&i!=y){
a[i]=query(i,x,y);
if(!mx) mx=i;
else if(a[i]>a[mx]) mx=i;
}
y=mx;
//printf("%d %d %d %d\n",x,y,z,t);
a=std::vector<int>(N+1,0);
mx=0;
for(int i=1;i<=N;++i) if(i!=x&&i!=y){
a[i]=query(i,x,y);
if(!mx) mx=i;
else if(a[i]>a[mx]) mx=i;
}
z=mx;
//printf("%d %d %d %d\n",x,y,z,t);
a=std::vector<int>(N+1,0);
mx=0;
int mn=0;
for(int i=1;i<=N;++i) if(i!=z&&i!=y){
a[i]=query(i,z,y);
if(!mx) mx=mn=i;
else{
if(a[i]>a[mx]) mx=i;
if(a[i]<a[mn]) mn=i;
}
}
x=mx;
t=mn;
//printf("%d %d %d %d\n",x,y,z,t);
if(x==t) return mkp(y,z);
if(!in(t,y,z)){
if(query(x,t,z)>query(x,t,y)) return mkp(x,z);
else return mkp(x,y);
}
int dyz=a[t]/2,dxyz=a[x]/2;
int dyxt=query(y,x,t)/2;
int dzxt=query(x,t,z)/2;
int dxy,dxz;
if(!in(t,x,y)){
dxz=dzxt;
dxy=dxyz*2-dyz-dzxt;
}else{
dxy=dzxt;
dxz=dxyz*2-dyz-dyxt;
}
if(std::max({dyz,dxy,dxz})==dyz) return mkp(y,z);
if(std::max({dyz,dxy,dxz})==dxy) return mkp(x,y);
return mkp(x,z);
}