#include"diameter.h"
#include<algorithm>
#include<utility>
#include<tuple>
std::pair<int,int> find_diameter(int task_id,int n) {
    if(n==1) {
        return {1,1};
    }
    if(n==2) {
        return {1,2};
    }
    if(n==3) {
        if(in(1,2,3)) {
            return {2,3};
        }
        if(in(2,1,3)) {
            return {1,3};
        }
        return {1,2};
    }
    const auto find([&](const int &x,const int &y)->std::tuple<std::tuple<int,int>,std::tuple<int,int>> {
        std::tuple<int,int> min(1000000000,0),max(-1000000000,0);
        for(int i=1;i<=n;i++) {
            if(i==x||i==y) {
                continue;
            }
            std::tuple<int,int> tmp(query(x,y,i),i);
            min=std::min(min,tmp);
            max=std::max(max,tmp);
        }
        return {min,max};
    });
    int a{std::get<1>(std::get<1>(find(1,2)))};
    int b{std::get<1>(std::get<1>(find(1,a)))};
    auto [r0,r1](find(a,b));
    auto &[d0,x](r0);
    auto &[s,c](r1);
    if(x==c) {
        return {a,b};
    }
    int d1{},d2{};
    if(in(x,a,c)) {
        d1=query(x,a,c),d2=s-d0-d1;
    }
    else {
        d2=query(x,b,c),d1=s-d0-d2;
    }
    if(d0>=d1&&d0>=d2) {
        return {a,b};
    }
    if(d1>=d2) {
        return {a,c};
    }
    return {b,c};
}