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

std::mt19937 rnd(std::random_device{}());

int getfarthest(int x, int n) {
  using namespace std;
  int y(rnd() % (n - 1));
  if (y >= x) ++y;
  vector<vector<int>> ps(n);
  for (int i(0); i != n; ++i)
    if (i != x && i != y)
      ps[query(i + 1, x + 1, y + 1) / 2].push_back(i);
  int di(0);
  while (ps[di].empty()) ++di;
  int fd(di), fp(y);
  if (di == 2) {
//  cout << "check " << x << ' ' << y << endl;
    if (ps[2].size() == 1 && in(ps[2][0] + 1, x + 1, y + 1))
      y = ps[2][0];
    else
      --fd;
    --di;
  }
  while (di != 1) {
    y = ps[di][rnd() % ps[di].size()];
    for (int z : ps[di])
      if (z != y) ps[query(z + 1, x + 1, y + 1) / 2].push_back(z);
    while (!ps[di - 1].empty()) --di;
    if (di == 2) {
      if (ps[2].size() == 1 && in(ps[2][0] + 1, x + 1, y + 1))
        y = ps[2][0];
      --di;
    }
  }
  for (int d(fd-- + 1); d != n; ++d)
    for (int z : ps[d]) {
      int ths(query(z + 1, x + 1, y + 1) / 2);
      if (ths > fd) fd = ths, fp = z;
    }
//cout << x << ' ' << fp << ' ' << fd << ' ' << y << endl;
  return fp;
}

std::pair<int, int> find_diameter(int subid, int n) {
  using namespace std;
  if (n == 1) return {1, 1};
  if (n == 2) return {1, 2};
  int x(rnd() % n);
  int y(getfarthest(x, n));
  return {y + 1, getfarthest(y, n) + 1};
}