#include"diameter.h"
#include<bits/stdc++.h>
using namespace std;
pair<int,int>find_diameter(int,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};else if(in(2,1,3))return {1,3};else return {1,2};
	int a=1,b=2,c=3,len=query(1,2,3),mn=0;
	vector<int>vlen(n+1);
	vlen[0]=1e9;
	for(int _=0;_<3;_++,swap(a,c),swap(a,b))
	{
		mn=0;
		for(int x=1;x<=n;x++)
		if(x!=b&&x!=c)
		{
			vlen[x]=query(x,b,c);
			if(vlen[x]>len)len=vlen[x],a=x;
			if(vlen[x]<=vlen[mn])mn=x;
		}
	}
	if(vlen[c]==vlen[mn])return {a,b};
	if(in(b,a,c))return {a,c};
	int l1=mn,l2,l3;
	if(in(mn,a,c))l2=query(mn,a,c),l3=2*len-l1-l2;
	else l3=query(mn,b,c),l2=2*len-l1-l3;
	if(l1==max({l1,l2,l3}))return {b,c};
	if(l2==max({l1,l2,l3}))return {a,c};
	if(l3==max({l1,l2,l3}))return {a,b};
}