#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);
}

pii find_diameter(int task_id, int n) {
    if (n <= 2) return mkpr(1, n);
    int u = 1, v = 2, w = 3;
    rep(i, 1, n) if (i != u && i != v && i != w)
        if (qry(u, v, w) < qry(i, v, w)) u = i;
    rep(i, 1, n) if (i != u && i != v && i != w)
        if (qry(u, v, w) < qry(u, i, w)) v = i;
    rep(i, 1, n) if (i != u && i != v && i != w)
        if (qry(u, v, w) < qry(u, v, i)) w = i;
    int x = 0;
    rep(i, 1, n) if (i != u && i != v && i != w)
        if (!x || qry(u, v, w) < qry(u, v, x)) x = w;
    cout << u << ' ' << v << ' ' << w << endl;
    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), b = qry(u, w, x), c = qry(u, v, w) - (a >> 1) - (b >> 1);
        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), b = qry(v, w, x), c = qry(u, v, w) - (a >> 1) - (b >> 1);
    int d = max({a, b, c});
    if (d == a) return mkpr(u, v);
    if (d == b) return mkpr(v, w);
    return mkpr(u, w);
}