#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 n,f[N],p[N];bool ban[N];
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);
	if(n>1e4)
	{
		iota(p+1,p+1+n,1);shuffle(p+1,p+1+n,rnd);fill(ban+1,ban+1+n,0);
		for(int i=1;i<=min(n,30);i++) ban[p[i]]=1;	
	}
	int x=1,y=2,z=3,d=query(1,2,3),mn=inf;
	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&&!ban[i])
	{
		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&&!ban[i])
	{
		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(),30);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(c2<2) d2=-1;if(c3<2) d3=-1;
	mx=max({d1,d2,d3});
	if(d1==mx) return {x,y};
	if(d2==mx) return {x,z};return {y,z};
}