#include"diameter.h"
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int fa[N], dep[N], cnt, p[N], pos[N], l[N], r[N];
vector<int> g[N];
void dfs(int u) {
	p[++cnt] = u, pos[u] = cnt;
	dep[u] = dep[fa[u]] + 1;
	l[u] = cnt;
	for (auto v : g[u])
		if (v != fa[u]) {
			fa[v] = u, dfs(v);
			p[++cnt] = u;
		}
	r[u] = cnt;
}

int lg[N];
std::pair<int, int> mn[N][20];
void init() {
	cnt = 0, dfs(1), lg[0] = -1;
	for (int i = 1; i <= cnt; i++) {
		mn[i][0] = std::make_pair(dep[p[i]], p[i]);
		lg[i] = lg[i >> 1] + 1;
	}
	for (int j = 1; j <= lg[cnt]; j++) {
		for (int i = 1; i <= cnt - (1 << j) + 1; i++) {
			mn[i][j] = std::min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
		}
	}
}
int lca(int x, int y) {
	int l = pos[x], r = pos[y];
	if (l > r) std::swap(l, r);
	int tmp = lg[r - l + 1];
	return std::min(mn[l][tmp], mn[r - (1 << tmp) + 1][tmp]).second;
}

void add(int x, int y){
	g[x].push_back(y);
}

int dis(int x, int y){
	return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}

pair<int, int> find_diameter(int subid, int n){
	for (int i = 1; i <= n; i++) g[i].clear();
	for (int x = 1; x <= n; x++){
		for (int y = x + 1; y <= n; y++){
			vector<int> cnt;
			for (int z = y + 1; z <= n; z++){
				int tp = query(x, y, z);
				if (tp == 4) cnt.push_back(z);
			}
			if (cnt.size()) add(x, y), add(y, x);
		}
	}
	init();
	int x = 1, y = 1;
	for (int i = 1; i <= n; i++)
		if (dis(x, i) > dis(x, y)) y = i;
	x = y, y = 1;
	for (int i = 1; i <= n; i++)
		if (dis(x, i) > dis(x, y)) y = i;
	return {x, y};
}