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

std::pair<int, int> 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};
    }
    if (in(2, 1, 3)) {
      return {1, 3};
    }
    return {1, 2};
  }
  if (n == 4) {
    int cnt = 0;
    for (int i = 1; i <= 4; i++) {
      for (int j = i + 1; j <= 4; j++) {
        for (int k = j + 1; k <= 4; k++) {
          cnt += query(i, j, k) == 4;
        }
      }
    }
    if (cnt == 3) {
      if (in(1, 2, 3)) {
        return {2, 3};
      }
      if (in(2, 1, 3)) {
        return {1, 3};
      }
      return {1, 2};
    }
    for (int i = 1; i <= 4; i++) {
      for (int j = i + 1; j <= 4; j++) {
        cnt = 0;
        for (int k = 1; k <= 4; k++) {
          if (i != k && j != k) {
            cnt += query(i, j, k) == 6;
          }
        }
        if (cnt == 2) {
          return {i, j};
        }
      }
    }
    assert(false);
  }

  int s = 0;
  std::vector d(6, std::vector(6, std::vector<int>(6)));

  auto A1 = [&](int i, int j, int k) {
    int a[3] = {i, j, k};
    std::sort(a, a + 3);
    return d[a[0]][a[1]][a[2]];
  };

  for (int i = 1; i <= 5; i++) {
    for (int j = i + 1; j <= 5; j++) {
      for (int k = j + 1; k <= 5; k++) {
        d[i][j][k] = query(i, j, k);
        s += d[i][j][k];
      }
    }
  }
  s /= 3;

  std::vector<std::map<int, int>> dis(n + 1);
  for (int i = 1; i <= 5; i++) {
    for (int j = i + 1; j <= 5; j++) {
      std::vector<int> t;
      for (int k = 1; k <= 5; k++) {
        if (i != k && j != k) {
          t.push_back(k);
        }
      }
      int v = A1(i, t[0], t[1]) + A1(j, t[0], t[1]) + A1(i, t[0], t[2]) + A1(j, t[0], t[2]) + A1(i, t[1], t[2]) + A1(j, t[1], t[2]);
      v /= 2;
      dis[i][j] = s - v;
    }
  }

  auto A2 = [&](int i, int j) {
    return dis[std::min(i, j)][std::max(i, j)];
  };

  int len = -1;
  int x, y, z;
  for (int i = 1; i <= 5; i++) {
    for (int j = i + 1; j <= 5; j++) {
      if (A2(i, j) > len) {
        len = A2(i, j);
        x = i;
        y = j;
      }
    }
  }
  for (int i = 1; i <= 5; i++) {
    if (i != x && i != y) {
      z = i;
      break;
    }
  }

  for (int i = 6; i <= n; i++) {
    int a = query(x, y, i);
    int b = query(x, z, i);
    int c = query(y, z, i);
    int d = a + b + c;
    d -= A2(x, y) + A2(x, z) + A2(y, z);
    d /= 2;
    dis[z][i] = d - (a - A2(x, y));
    dis[y][i] = d - (b - A2(x, z));
    dis[x][i] = d - (c - A2(y, z));
    if (dis[x][i] > len) {
      len = dis[x][i];
      z = y;
      y = i;
    }
    if (dis[y][i] > len) {
      len = dis[y][i];
      z = x;
      x = i;
    }
  }
  return {x, y};
}