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

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T> void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T> void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 100010;

int val[maxn];

pii find_diameter(int sid, int n) {
  if (n == 1) return pii(1, 1);
  if (n == 2) return pii(1, 2);
  if (n == 3) {
    if (in(1, 2, 3)) return pii(2, 3);
    if (in(2, 1, 3)) return pii(1, 3);
    return pii(1, 2);
  }
  int x = 1, y = 2, z = 3, mxid = 0, mx = 0;
  rep (i, 1, n) if (i != y && i != z) {
    int cur = query(i, y, z);
    if (cur >= mx) mx = cur, mxid = i;
  }
  x = mxid;
  mxid = mx = 0;
  rep (i, 1, n) if (i != x && i != z) {
    int cur = query(i, x, z);
    if (cur >= mx) mx = cur, mxid = i;
  }
  y = mxid;
  mxid = mx = 0;
  int mn = 1e9, t = 0;
  rep (i, 1, n) if (i != x && i != y) {
    int cur = query(i, x, y);
    if (cur >= mx) mx = cur, mxid = i;
    if (cur < mn) mn = cur, t = i;
    val[i] = cur;
  }
  z = mxid;
  if (val[z] == mn) return pii(x, y);
  if (in(y, x, z)) return pii(x, z);
  int disxy = mn, disxz, disyz;
  if (in(t, x, z)) disxz = query(x, t, z), disyz = 2 * mx - disxy - disxz;
  else disyz = query(y, t, z), disxz = 2 * mx - disxy - disyz;
  int res = max({disxy, disxz, disyz});
  if (disxy == res) return pii(x, y);
  if (disxz == res) return pii(x, z);
  return pii(y, z);
}