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

const int N = 3e5 + 10;
int d[N], vis[N]; vector<int> node; 
int StepOne(int n) {
    node.clear(); int mnd = 1e9;
    for (int i = 3; i <= n; i++) {
        d[i] = query(1, 2, i) / 2;
        if (d[i] < mnd) {
            node.clear();
            mnd = d[i];
        } 
        if (d[i] == mnd) node.emplace_back(i);
    } 
    for (int i = 1; i <= n; i++) vis[i] = 0;
    vis[1] = 1;
    
    if (mnd == 2 && in(2, 1, node.front())) return 2;
    int dist = node.size();

    for (int v : node) vis[v] = 1;
    
    for (int i = 0; i < dist; i += 2) {
        if (i == dist - 1) return node[i];
        if (query(node[i], node[i + 1], 2) / 2 == dist) {
            if (in(node[i], 1, node[i + 1])) return node[i];
            else return node[i + 1];
        }
    }

}
std::pair<int, int> find_diameter(int subid, int n) {
    if (n == 1) return {1, 1};
    if (n == 2) return {1, 2};
    int x = StepOne(n);
    int s = 0, vl = -1;
    for (int i = 1; i <= n; i++) {
        if (i == 1) d[i] = 0;
        else if (i == x) d[i] = 0;
        else if (vis[i]) d[i] = -1;
        else d[i] = query(1, x, i) / 2 - 1;
        if (d[i] > vl) {
        	vl = d[i];
        	s = i;
		}
    }
    int BS = 1, BT = x;
    
    if (in(x, 1, s)) swap(BS, BT);
    
    int t = 0, val = -1;
    auto upd = [&] (int u, int v) {
        if (v > val) t = u, val = v;
    };
    for (int i = 1; i <= n; i++) {
        if (i == BS) upd(i, d[s]);// d[s]
        else if (i == BT) upd(i, d[s] + 1); // d[s] + 1
        else if (i == s) upd(i, 0); // 0
        else if (vis[i]) continue;
        else {
            int dsi = query(BS, s, i) / 2;
            if (dsi == d[s] + d[i] + 1) upd(i, dsi);
            else upd(i, 2 * dsi - d[s] - d[i]); // 2 * dsi - d[s] - d[i]
		}
    }
    for (int i = 1; i <= n; i++) vis[i] = d[i] = 0;
    node.clear();
    return {s, t};
}