#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;
const int N=1e5+5;
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,1e9+1);
	int x=1,y=2,z=3,d=-1,mn=1e9;
	for(int i=1;i<=n;i++) if(i!=x&&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!=y&&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&&i!=z)
	{
		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;
	// for(int i=1;i<=n;i++) if(f[i]==mn) g.push_back(i);
	// for(int i:g)
	for(int i=1;i<=n;i++)
	{
		if(f[i]+query(x,z,i)+query(y,z,i)==2*d)
		{
			int p=mn,q=query(x,z,i),r=query(y,z,i),mx=max({p,q,r});
			if(p==mx) return {x,y};
			if(q==mx) return {x,z};
			return {y,z};
		}
	}
	return {x,y};
}