#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,U=100;
int n,f[N],p[N];bool ban[N];
inline void R()
{
	if(n<=1e4) return;
	shuffle(p+1,p+1+n,rnd);fill(ban+1,ban+1+n,0);
	for(int i=1;i<=min(n,U<<1);i++) ban[p[i]]=1;
}
P find_diameter(int id,int n)
{
	::n=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);iota(p+1,p+1+n,1);
	int x=1,y=2,z=3,d=query(1,2,3),mn=inf;R();
	for(int i=1;i<=n;i++) if(i!=y&&i!=z&&!ban[i])
	{
		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>d) d=D,z=i;
	}
	if(f[z]==mn) return {x,y};
	bool o1=in(x,y,z),o2=in(y,x,z);
	if(o1) return {y,z};if(o2) return {x,z};
	vector<int>g;int d1=mn,d2=inf,d3=inf,mx,c2=1,c3=1;
	for(int i=1;i<=n;i++) if(f[i]==mn) g.push_back(i);
	shuffle(g.begin(),g.end(),rnd);
	for(int i=0;i<min((int)g.size(),U);i++)
	{
		int n2=query(x,z,g[i]),n3=query(y,z,g[i]);
		c2+=(n2==d2);c3+=(n3==d3);
		if(n2<d2) c2=1,d2=n2;if(n3<d3) c3=1,d3=n3;
	}
	if(g.size()>U){if(c2<=5) d2=-1;if(c3<=5) d3=-1;}
	mx=max({d1,d2,d3});
	if(d1==mx) return {x,y};
	if(d2==mx) return {x,z};return {y,z};
}