//                      위대한    -    주의 만세!
#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);}

std::pair<int,int> 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);
}