#include "diameter.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
constexpr int inf = 1e9;
int d[10][10][10];
pii find(vector<int>v)
{
	if (v.size() == 1) return pii(v[0], v[0]);
	if (v.size() == 2) return pii(v[0], v[1]);
	if (v.size() == 3) {
		if (in(v[0], v[1], v[2])) return pii(v[1], v[2]);
		if (in(v[1], v[0], v[2])) return pii(v[0], v[2]);
		return pii(v[0], v[1]);
	}
	for (int i = 0; i < v.size(); ++i) {
		for (int j = i + 1; j < v.size(); ++j) {
			for (int k = j + 1; k < v.size(); ++k) {
				d[i][j][k] = query(v[i], v[j], v[k]);
				d[i][k][j] = d[i][j][k];
				d[j][i][k] = d[i][j][k];
				d[j][k][i] = d[i][j][k];
				d[k][i][j] = d[i][j][k];
				d[k][j][i] = d[i][j][k];
			}
		}
	}
	pair<int, pii>mx;
	for (int i = 0; i < v.size(); ++i) {
		for (int j = i + 1; j < v.size(); ++j) {
			int lst = -1, mn = inf;
			bool is4 = 1;
			for (int k = 0; k < v.size(); ++k) {
				if (k != i && k != j) {
					mn = min(mn, d[i][j][k]);
					is4 &= (d[i][j][k] == 4);
					lst = k;
				}
			}
			if (is4) {
				mx = max(mx, make_pair(4, pii(v[i], v[lst])));
			}
			mx = max(mx, make_pair(mn, pii(v[i], v[j])));
		}
	}
	return mx.second;
}
pii find_diameter(int subid, int n) {
	if (n <= 5) {
		vector<int>v;
		for (int i = 1; i <= n; ++i) v.emplace_back(i);
		return find(v);
	}
	vector<int>v;
	for (int i = 1; i <= 5; ++i) v.emplace_back(i);
	auto [x, y] = find(v);
	for (int i = 6; i <= n; i += 3) {
		v.resize(5);
		v[0] = x, v[1] = y, v[2] = i, v[3] = i + 1, v[4] = i + 2;
		while (v.back() > n) v.pop_back();
		auto [x, y] = find(v);
	}
	return pii(x, y);
}