#include "diameter.h"
#include <bits/stdc++.h>
using namespace std;

pair<int, int> find_diameter(int subid, int n) {
    int x=1,y=2,z=3;
    int now=query(x,y,z);
    for(int i=1;i<=n;i++){
        if(i==x||i==y||i==z) continue;
        int len=query(i,y,z);
        if(len>now){
            x=i;
            now=len;
        }
    }
    for(int i=1;i<=n;i++){
        if(i==x||i==y||i==z) continue;
        int len=query(x,i,z);
        if(len>now){
            y=i;
            now=len;
        }
    }
    for(int i=1;i<=n;i++){
        if(i==x||i==y||i==z) continue;
        int len=query(x,y,i);
        if(len>now){
            z=i;
            now=len;
        }
    }
    if(n<=50000){
        int L=now,X=x,Y=y,Z=z;
        for(int i=1;i<=n;i++){
            if(i==x||i==y||i==z) continue;
            int len=query(i,y,z);
            if(len<now){
                x=i;
                now=len;
            }
        }
        int yz=now;
        swap(x,X);
        now=L;
        
        for(int i=1;i<=n;i++){
            if(i==x||i==y||i==z) continue;
            int len=query(x,i,z);
            if(len<now){
                y=i;
                now=len;
            }
        }
        int xz=now;
        swap(y,Y);
        now=L;
        
        for(int i=1;i<=n;i++){
            if(i==x||i==y||i==z) continue;
            int len=query(x,y,i);
            if(len<now){
                z=i;
                now=len;
            }
        }
        int xy=now;
        swap(z,Z);
        now=L;
        
        if(xy>=yz&&xy>=xz){
            z=Z;
        }
        else if(xz>=xy&&xz>=yz){
            y=Y;
        }
        else x=X;
        if(in(x,y,z)){
            return {y,z};
        }
        else if(in(y,x,z)){
            return {x,z};
        }
        return {x,y};
    }
}
/*
0 1
5
1 2
2 3
1 4
1 5

g++ grader.cpp diameter.cpp -o diameter -O2 -lm
*/