#include "diameter.h"
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> pii;

int cnt, cur, t[10][10], dis[10][10];
pii s[15]; double a[15][15];
void Solve() {
  cnt = cur = 0;
  F(i, 1, 5) F(j, i + 1, 5)
    s[cnt] = {i, j}, t[i][j] = t[j][i] = cnt, ++cnt;
  F(i, 1, 5) F(j, i + 1, 5) F(k, j + 1, 5)
    a[cur][t[i][j]] = a[cur][t[i][k]] = a[cur][t[j][k]] = 1,
    a[cur][10] = query(i, j, k), ++cur;
  F(i, 0, 9) {
    int l = i; while (l < 9 && a[l][i] == 0) ++l;
    F(j, 0, 10) swap(a[i][j], a[l][j]);
    double del = a[i][i];
    F(j, 0, 10) a[i][j] /= del;
    F(j, 0, 9) if (i != j) {
      del = a[j][i];
      F(k, 0, 10) a[j][k] -= del * a[i][k];
    }
  }
  F(i, 0, 9) {
    int u = s[i].first, v = s[i].second;
    dis[u][v] = dis[v][u] = a[i][10];
  }
}

pii find_diameter(int task_id, int n) {
  if (n == 1) return {1, 1};
  if (n == 2) return {1, 2};
  if (n == 3)
    if (in(1, 2, 3)) return {2, 3};
    else if (in(2, 1, 3)) return {1, 3};
    else return {1, 2};
  if (n == 4) {
    int x = query(1, 2, 3), y = query(1, 2, 4);
    int z = query(1, 3, 4), w = query(2, 3, 4);
    int cnt = (x == 6) + (y == 6) + (z == 6) + (w == 6);
    if (cnt == 1)
      if (x == 6 || y == 6) return {1, 2};
      else return {3, 4};
    else
      if (x == 6 && y == 6) return {1, 2};
      else if (x == 6 && z == 6) return {1, 3};
      else if (x == 6 && w == 6) return {2, 3};
      else if (y == 6 && z == 6) return {1, 4};
      else if (y == 6 && w == 6) return {2, 4};
      else return {3, 4};
  }
  Solve();
  int st = 2, ed = 1, u = 0;
  F(i, 1, 5) if (i != 1 && dis[1][i] > dis[1][st]) st = i;
  F(i, 1, 5) if (i != st && dis[st][i] > dis[st][ed]) ed = i;
  F(i, 1, 5) if (i != st && i != ed) u = i;
  int dd = dis[st][ed], d1 = dis[st][u], d2 = dis[ed][u];
  F(i, 6, n) {
    int q = query(i, st, ed) - dd, q1 = query(i, st, u) - d1, q2 = query(i, ed, u) - d2;
    int qq = (q + q1 + q2) / 2, nd1 = qq - q2, nd2 = qq - q1, ndu = qq - q;
    if (nd1 >= nd2 && nd1 > dd) ed = i, dd = nd1, d2 = ndu;
    if (nd2 > nd1 && nd2 > dd) st = i, dd = nd2, d1 = ndu;
  }
  return {st, ed};
}