#include "diameter.h"
#include <bits/stdc++.h>

namespace Mine {
    void gauss(int imt[][11], int rs[]){
        double mt[10][11];
        for (int i = 0; i < 10; ++i)std::copy_n(imt[i], 11, mt[i]);
        for (int i = 0; i < 10; ++i){
            int t = i;
            for (int j = i + 1; j < 10; ++j)
                if (std::fabs(mt[j][i]) > 1e-6)t = j;
            std::swap(mt[i], mt[t]);
            assert(std::fabs(mt[i][i]) > 1e-6);
            double ml = 1. / mt[i][i];
            for (double &rf : mt[i])rf *= ml;
            for (int j = 0; j < 10; ++j)if (j ^ i){
                double sb = mt[j][i];
                for (int k = 0; k < 11; ++k)
                    mt[j][k] -= sb * mt[i][k];
            }
        }
        for (int i = 0; i < 10; ++i)rs[i] = round(mt[i][10]), assert(std::fabs(mt[i][10] - rs[i]) <= 1e-6);
    }
    void get_dis_of_first_five(int dis[6][6]){
        std::map<std::pair<int, int>, int> Mp;//choose 2 from 5
        for (int i = 1, _ = 0; i <= 4; ++i)
            for (int j = i + 1; j <= 5; ++j, ++_)
                Mp.emplace(std::make_pair(i, j), _);
        static int mt[10][11]; memset(mt, 0, sizeof(mt));
        for (int i = 1, _ = 0; i <= 3; ++i)
            for (int j = i + 1; j <= 4; ++j)
                for (int k = j + 1; k <= 5; ++k, ++_){
                    mt[_][Mp[{i, j}]] = mt[_][Mp[{i, k}]] = mt[_][Mp[{j, k}]] = 1;
                    mt[_][10] = query(i, j, k);
                }
        static int rs[10];
        gauss(mt, rs);
        for (int i = 1; i <= 5; ++i){
            for (int j = 1; j <= 5; ++j){
                if (i == j)dis[i][j] = 0;
                else if (i > j)dis[i][j] = rs[Mp[{j, i}]];
                else dis[i][j] = rs[Mp[{i, j}]];
            }
        }
    }
}

std::pair<int, int> find_diameter(int subid, int n) {
    using std::pair;
    using std::make_pair;

    if (n <= 2)return make_pair(1, n);
    if (n == 3){
        if (in(1, 2, 3))return make_pair(2, 3);//2-1-3
        if (in(2, 1, 3))return make_pair(1, 3);//1-2-3
        return make_pair(1, 2);//1-3-2
    }
    if (n == 4){
        int ds[5] = {0, query(2, 3, 4), query(1, 3, 4), query(1, 2, 4), query(1, 2, 3)};
        int a[] = {ds[1], ds[2], ds[3], ds[4]};std::sort(a, a + 4);
        if (a[2] == 6){//4,4,6,6 : list
            int p = std::find(ds + 1, ds + 5, 4) - ds, q = std::find(ds + p + 1, ds + 5, 4) - ds;
            return make_pair(p, q);
        } else {//4,4,4,6 : flower
            int md = std::find(ds + 1, ds + 5, 6) - ds;//root of flower
            return md == 1? make_pair(2, 3) : md == 2? make_pair(1, 3) : make_pair(1, 2);
        }
    }

    //n >= 5
    int p = 1, q = 1, r;//rs = p-q, r != p, r != q
    int dpq = 0, dpr, dqr;//distance
    {
        static int dis[6][6];
        Mine::get_dis_of_first_five(dis);
        for (int i = 1; i <= 5; ++i){
            int j = std::max_element(dis[i] + 1, dis[i] + 6) - dis[i];
            if (dis[i][j] > dpq)dpq = dis[i][j], p = i, q = j;
        }
        r = (p == 1 || q == 1? p == 2 || q == 2? 3 : 2 : 1);
        dpr = dis[p][r];dqr = dis[q][r];
    }
    for (int nw = 6; nw <= n; ++nw){//add point
        int npq = query(nw, p, q), npr = query(nw, p, r), nqr = query(nw, q, r);
        int dnp, dnq, dnr;
        {
            //dnp+dnq = npq-dpq
            //dnp+dnr = npr-dpr
            //dnq+dnr = nqr-dqr
            int A = npq - dpq, B = npr - dpr, C = nqr - dqr;
            int S = A + B + C >> 1;
            dnp = S - C, dnq = S - B, dnr = S - A;
        }
        int mxds = std::max({dpq, dnp, dnq});
        assert(dnr <= mxds);
        if (mxds == dpq)continue;//no change
        if (mxds == dnp)std::tie(p, q, r, dpq, dpr, dqr) = std::make_tuple(p, n, r, dnp, dpr, dnr);
        else std::tie(p, q, r, dpq, dpr, dqr) = std::make_tuple(n, q, r, dnq, dnr, dqr);
    }
    return make_pair(p, q);
}