#include "diameter.h"
#include <bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
mt19937 rnd(time(0));
const int N=1e5+5,inf=1e9;
int f[N];
P find_diameter(int id,int n)
{
  if(n==1) return {1,1};
  if(n==2) return {1,2};
  if(n==3)
  {
    bool o1=in(1,2,3),o2=in(2,1,3);
    if(o1) return {2,3};
    if(o2) return {1,3};return {1,2};
  }
  int x=1,y=2,z=3,d=query(1,2,3),mn=inf,t;
  for(int i=1;i<=n;i++) if(i!=y&&i!=z)
  {
    int D=query(i,y,z);
    if(D>d) d=D,x=i;
  }
  for(int i=1;i<=n;i++) if(i!=x&&i!=z)
  {
    int D=query(x,i,z);
    if(D>d) d=D,y=i;
  }
  for(int i=1;i<=n;i++) if(i!=x&&i!=y)
  {
    int D=query(x,y,i);mn=min(mn,f[i]=D);
    if(D==mn) t=i;
    if(D>d) d=D,z=i;
  }
  if(f[z]==mn) return {x,y};
  if(in(y,x,z)) return {x,z};
  int disxy=mn,disxz,disyz,mx;
  if(in(t,x,z)) disxz=query(x,t,z),disyz=2*d-disxy-disxz;
  else disyz=query(y,t,z),disxz=2*d-disxy-disyz;
  mx=max({disxy,disxz,disyz});
  if(disxy==mx) return {x,y};
  if(disxz==mx) return {x,z};
  if(disyz==mx) return {y,z};
  
}