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

using namespace std;

const int N = 1e5 + 5;

int n, dis[N];

inline void Find(int a, int b, int &c, int &d)
{
    c = d = 0;
    for(int i = 1; i <= n; i ++ )
    {
        if(i == a || i == b)
        {
            dis[i] = -1;
        }
        else
        {
            dis[i] = query(a, b, i);
            if(!c)
            {
                c = d = i;
            }
            else
            {
                if(dis[i] > dis[c]) c = i;
                if(dis[i] < dis[d]) d = i;
            }
        }
    }
}

std::pair<int, int> find_diameter(int subid, int _n)
{
    n = _n;
    if(n == 1) return make_pair(1, 1);
    if(n == 2) return make_pair(1, 2);
    if(n == 3)
    {
        if(in(1, 2, 3)) return make_pair(2, 3);
        if(in(2, 1, 3)) return make_pair(1, 3);
        return make_pair(1, 2);
    }

    int a = 1, b = 2, c, d = 0;
    Find(a, b, c, d);
    Find(a, c, b, d);
    Find(b, c, a, d);

    if(!in(d, b, c)) return make_pair(a, d);
    int dab, dac, dbc = dis[d] / 2;
    if(in(d, a, b))
    {
        dab = query(d, a, b) / 2;
        dac = dis[a] - dab - dbc;
    }
    else
    {
        dac = query(d, a, c) / 2;
        dab = dis[a] - dac - dbc;
    }

    if(dab > dac && dab > dbc) return make_pair(a, b);
    if(dac > dbc) return make_pair(a, c);
    return make_pair(b, c);
}