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

typedef long long ll;
const int K=1e5+3;
mt19937 rd(time(0));
int Ask(int x,int y,int z){assert(x!=y&&x!=z&&y!=z);return query(x,y,z)/2;}
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);
	if(n==3)
	{
		if(in(1,2,3))return make_pair(2,3);
		if(in(2,1,3))return make_pair(1,3);
		return make_pair(1,2);
	}
	int X=rd()%n+1,Y=rd()%(n-1)+1,Mn=1e9,cnt=0,Z=0;Y+=Y>=X;
	vector<int>dis(n+1,0),typ(n+1,0);typ[X]=typ[Y]=2;
	for(int i=1;i<=n;i++)if(i!=X&&i!=Y)dis[i]=Ask(i,X,Y),Mn=min(Mn,dis[i]);
	for(int i=1;i<=n;i++)if(i!=X&&i!=Y&&dis[i]==Mn)typ[i]=1,cnt++;
	if(cnt==1)Z=find(typ.begin()+1,typ.end(),1)-typ.begin();
	else if(Mn==2)
	{
		for(int i=1;i<=n;i++)typ[i]=0;
		for(int i=1;i<=n;i++)if(i!=X&&i!=Y&&dis[i]==Mn)
		{
			Z=i;
			if(in(X,Y,Z))swap(X,Z);
			else swap(Y,Z);
			break;
		}
		typ[X]=typ[Y]=2;typ[Z]=1;
	}
	else if(cnt==2)
	{
		int tx=0,ty=0;
		for(int i=1;i<=n;i++)if(typ[i]==1)!tx?tx=i:ty=i;
		Z=in(tx,X,ty)?ty:tx;
	}
	else
	{
		Z=find(typ.begin()+1,typ.end(),1)-typ.begin();
		vector<int>val(n+1,0);int Mx=0;
		for(int i=1;i<=n;i++)if(typ[i]==1&&i!=Z)
			val[i]=Ask(X,Z,i),Mx=max(Mx,val[i]);
		if(count(val.begin()+1,val.end(),Mx)<cnt-1)
			for(int i=1;i<=n;i++)if(typ[i]==1&&i!=Z&&val[i]==Mx){Z=i;break;}
	}
	vector<int>val(n+1,0);int Mx=0,ans1=0;
	for(int i=1;i<=n;i++)if(!typ[i]||i==X)val[i]=Ask(i,Y,Z),Mx=max(Mx,val[i]);
	for(int i=1;i<=n;i++)if((!typ[i]||i==X)&&val[i]==Mx)ans1=i;
	vector<int>res(n+1,0);int ans2=Y,W=0;
	if(in(Z,ans1,Y))W=Z;
	else W=Y;
	for(int i=1;i<=n;i++)if(typ[i]!=1&&i!=Y&&i!=ans1)
	{
		int v=Ask(ans1,W,i);
		if(v==val[i]+val[ans1]-1)res[i]=v;
		else res[i]=v+1-val[i]+v+1-val[ans1];
		Mx=max(Mx,res[i]);
	}
	for(int i=1;i<=n;i++)if(typ[i]!=1&&i!=ans1&&i!=Y&&res[i]==Mx)ans2=i;
	return make_pair(ans1,ans2);
}