#include <bits/stdc++.h>
#include <bits/extc++.h>
#include "diameter.h"
using namespace std;
#define ll long long
#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)
int n, m;
__gnu_pbds::gp_hash_table<ll, int> mp;
int qry(int u, int v, int w) {
if (u > v) swap(u, v);
if (v > w) swap(v, w);
if (u > v) swap(u, v);
ll x = u * 1000000000000 + v * 1000000 + w;
if (mp[x]) return mp[x];
return mp[x] = query(u, v, w);
}
pii find_diameter(int task_id, int n) {
mp.clear();
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, i) < qry(u, v, x)) x = i;
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(u, v, x)) return mkpr(v, w);
if (in(x, u, w)) swap(u, v);
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);
}