#include "diameter.h"
#include <bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
mt19937 rnd(time(0));
const int N=1e5+5,inf=1e9;
int f[N];
P find_diameter(int id,int n)
{
	if(n==1) return {1,1};
	if(n==2) return {1,2};
	if(n==3)
	{
		bool o1=in(1,2,3),o2=in(2,1,3);
		if(o1) return {2,3};
		if(o2) return {1,3};return {1,2};
	}fill(f+1,f+1+n,inf+1);
	int x=1,y=2,z=3,d=query(1,2,3),mn=inf,t;
	for(int i=1;i<=n;i++) if(i!=y&&i!=z)
	{
		int D=query(i,y,z);
		if(D>d) d=D,x=i;
	}
	for(int i=1;i<=n;i++) if(i!=x&&i!=z)
	{
		int D=query(x,i,z);
		if(D>d) d=D,y=i;
	}
	for(int i=1;i<=n;i++) if(i!=x&&i!=y)
	{
		int D=query(x,y,i);mn=min(mn,f[i]=D);
		if(D==mn) t=i;
		if(D>d) d=D,z=i;
	}
	if(f[z]==mn) return {x,y};
	if(in(y,x,z)) return {x,z};
	bool o=in(t,x,z);int d1=mn,d2,d3,mx;
	if(o) d2=query(x,t,z),d3=2*d-d1-d2;
	else d3=query(y,t,z),d2=2*d-d1-d3;
	int D2=inf,D3=inf;
	for(int i=1;i<=n;i++) if(f[i]==mn) D2=min(D2,query(x,z,i)),D3=min(D3,query(y,z,i));
	if(D2!=d2||D3!=d3) assert(0);
	mx=max({d1,d2,d3});
	if(d1==mx) return {x,y};
	if(d2==mx) return {x,z};return {y,z};
}