#include<bits/stdc++.h>
#include "diameter.h"
using namespace std;
int cal(int x,int y,int n){
	int d=1e9;
	int _=0;
	for(int i=1;i<=n;i++){
		if(i==x||i==y)continue;
		int dd=query(x,y,i);
		if(dd<d){
			d=dd;
			_=i;
		}
	}
	if(!in(_,x,y))d=1;
	while(d>1){
		for(int i=1;i<=n;i++){
			if(i==x||i==y)continue;
			int dd=query(x,y,i);
			if(dd<=d){
				d=dd;
				y=i;
				break;
			}
		}
	}
	int mx=0;
	int u=y;
	for(int i=1;i<=n;i++){
		if(i==x||i==y)continue;
		int dd=query(i,x,y);
		if(dd>mx){
			mx=dd;
			u=i;
		}
	}
	return u;
}
std::pair<int, int> find_diameter(int subid, int n) {
	if(n==1)return make_pair(1,1);
	if(n==2)return make_pair(1,2);
	int u=cal(1,2,n);
	int v=cal(u,2,n);
	return make_pair(u,v);
}