#include "diameter.h"
#include<bits/stdc++.h>
using namespace std;
namespace staring
{
    typedef long long LL;
    typedef vector<int> VEC;
    typedef pair<int,int> PII;
    typedef pair<LL,LL> PLL;
    #define fir first
    #define sec second

    #define FOR(i,a,b) for(int i=(a),__i=(b);i<=__i;i++)
    #define ROF(i,a,b) for(int i=(a),__i=(b);i>=__i;i--)

    template<typename TYPE>
    TYPE gmax(TYPE &x,const TYPE y){return x<y?x=y:x;}
    template<typename TYPE>
    TYPE gmin(TYPE &x,const TYPE y){return y<x?x=y:x;}

    static constexpr int SIZE=1<<20;
    static char buffin[SIZE]{},*pin1{},*pin2{};
    static char buffout[SIZE]{},*pout{buffout};
    #define GETC() (pin1==pin2&&(pin2=(pin1=buffin)+fread(buffin,1,SIZE,stdin),pin1==pin2)?EOF:*pin1++)
    #define PUTC(c) (pout-buffout==SIZE&&(fwrite(buffout,1,SIZE,stdout),pout=buffout),*pout++=c)
    template<typename TYPE>
    void read(TYPE &x)
    {
        static int signf{0},chin{0};
        x=signf=0,chin=GETC();
        while(chin<'0'||chin>'9')signf|=chin=='-',chin=GETC();
        while(chin>='0'&&chin<='9')x=(x<<3)+(x<<1)+(chin^48),chin=GETC();
        if(signf)x=-x;
    }
    template<typename TYPE>
    void write(TYPE x,char ch=' ',bool f=0)
    {
        static char stack[64]{},top{0};
        !x&&PUTC('0'),x<0&&(x=-x,PUTC('-'));
        while(x)stack[top++]=x%10|48,x/=10;
        while(top)PUTC(stack[--top]);
        if(ch)PUTC(ch);
    }

}using namespace staring;

PII find_diameter(int subid, int n)
{
    if(n==1)return {1,1};
    if(n==2)return {1,2};

    int x=1,y=2,z=3;
    VEC dxy(n+1),dxz(n+1),dyz(n+1),dz(n+1);
    FOR(i,3,n)
    {
        dxy[i]=query(x,y,i);
        if(dxy[i]>dxy[z])z=i;
    }

    int a=0,b=0;
    FOR(i,1,n)
    {
        if(i!=x&&i!=z)
        {
            dxz[i]=query(x,z,i);
            if(!a||dxz[i]<dxz[a])a=i;
        }
        if(i!=y&&i!=z)
        {
            dyz[i]=query(y,z,i);
            if(!b||dyz[i]<dyz[b])b=i;
        }
    }

    int disxz=0,disyz=0,disxy=0;
    disxz=in(a,x,z)?dxz[a]>>1:1;
    disyz=in(b,y,z)?dyz[b]>>1:1;
    disxy=dxy[z]-disxz-disyz;
    dz[x]=disxz,dz[y]=disyz;

    int c=z;a=b=0;
    FOR(i,1,n)
    {
        if(i!=x&&i!=y&&i!=z)
           dz[i]=(dxz[i]+dyz[i]-dxy[i]+disxy)>>1;
        if(dz[i]>dz[c])c=i;
        if(i!=x&&i!=z&&(!a||dxz[i]>dxz[a]))a=i;
        if(i!=y&&i!=z&&(!b||dyz[i]>dyz[b]))b=i;
    }

    if(a==b)return {z,c};
    return dz[c]>query(a,b,z)-dz[a]-dz[b]?(PII){z,c}:(PII){a,b};
}