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

#define pii pair<int, int>
#define mkpr make_pair
#define vi vector<int>
#define all(c) (c).begin(), (c).end()
#define rep(i, l, r) for (int i(l), i##End(r); i <= i##End; i = -~i)
#define ti3 tuple<int, int, int>

int n, m;
map<ti3, int> mp;

int qry(int u, int v, int w) {
    vi _({u, v, w}); sort(all(_));
    u = _[0], v = _[1], w = _[2];
    ti3 x(u, v, w);
    if (mp.count(x)) return mp[x];
    return mp[x] = query(u, v, w);
}


mt19937 gen(random_device{}());

int rnd(int l, int r) { return gen() % (r - l + 1) + l; }

pii find_diameter(int task_id, int n) {
    mp.clear();
    if (n <= 2) return mkpr(1, n);
    int u = rnd(1, n), v, w;
    while ((v = rnd(1, n)) == u);
    while ((w = rnd(1, n)) == v || w == u);
    rep(i, 1, n) if (i != u && i != v && i != w) {
        // printf("@ %d: (%d %d %d) (%d %d %d) -> ", i, u, v, w, i, v, w);
        if (qry(u, v, w) < qry(i, v, w)) u = i;
        // printf("(%d %d %d)\n", u, v, w);
    }
    rep(i, 1, n) if (i != u && i != v && i != w) {
        // printf("# %d: (%d %d %d) (%d %d %d) -> ", i, u, v, w, i, v, w);
        if (qry(u, v, w) < qry(u, i, w)) v = i;
        // printf("(%d %d %d)\n", u, v, w);
    }
    rep(i, 1, n) if (i != u && i != v && i != w) {
        // printf("$ %d: (%d %d %d) (%d %d %d) -> ", i, u, v, w, i, v, w);
        if (qry(u, v, w) < qry(u, v, i)) w = i;
        // printf("(%d %d %d)\n", u, v, w);
    }
    int x = 0;
    rep(i, 1, n) if (i != u && i != v && i != w)
        if (!x || qry(u, v, i) < qry(u, v, x)) x = i;
    printf("%d %d %d | %d\n", u, v, w, x);
    // for (auto [_, x] : mp) {
    //     auto [_u, _v, _w] = _;
    //     printf("[%d %d %d]: %d\n", _u, _v, _w, x);
    // }
    if (!x) {
        if (in(u, v, w)) return mkpr(v, w);
        if (in(v, u, w)) return mkpr(u, w);
        return mkpr(u, v);
    }
    if (in(x, u, w)) {
        int a = qry(u, v, x) >> 1, b = qry(u, w, x) >> 1, c = qry(u, v, w) - a - b;
        int d = max({a, b, c});
        if (d == a) return mkpr(u, v);
        if (d == b) return mkpr(u, w);
        return mkpr(v, w);
    }
    int a = qry(u, v, x) >> 1, b = qry(v, w, x) >> 1, c = qry(u, v, w) - a - b;
    int d = max({a, b, c});
    if (d == a) return mkpr(u, v);
    if (d == b) return mkpr(v, w);
    return mkpr(u, w);
}