#include "diameter.h"
#include<bits/stdc++.h>
using namespace std;
int b[15][15],d[15][15],p[15];
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);
	}
	if(n==4){
		int he=query(1,2,3),x=1,y=2,z=3;
		for(int i=4;i<=n;++i){
			int A=query(y,z,i),B=query(x,z,i),C=query(x,y,i);
			if(A>=B&&A>=C){
				if(A>he)he=A,x=i;
			}else if(B>=A&&B>=C){
				if(B>he)he=B,y=i;
			}else if(C>he)he=C,z=i;
		}
		he/=2;
		int mn=1e9,w=0;
		for(int i=1;i<=n;++i)if(i!=x&&i!=y&&i!=z){
			int hh=query(i,x,y);
			if(mn>hh)mn=hh,w=i;
		}
		mn/=2;
		int C=he-mn,A=0,B=0;
		if(in(w,x,z))B=he-query(w,x,z)/2,A=he-B-C;
		else A=he-query(w,y,z)/2,B=he-A-C;
		if(A<=B&&A<=C)return make_pair(y,z);
		if(B<=A&&B<=C)return make_pair(x,z);
		return make_pair(x,y);
	}
	int b123=query(1,2,3),b124=query(1,2,4),b125=query(1,2,5);
	int b134=query(1,3,4),b135=query(1,3,5),b145=query(1,4,5);
	int b234=query(2,3,4),b235=query(2,3,5),b245=query(2,4,5);
	int b345=query(3,4,5),he=b123+b124+b125+b134+b135+b145+b234+b235+b245+b345;
	b[1][2]=(b123+b124+b125+b345-he/3)/2;
	b[1][3]=(b123+b134+b135+b245-he/3)/2;
	b[1][4]=(b124+b134+b145+b235-he/3)/2;
	b[1][5]=(b125+b135+b145+b234-he/3)/2;
	b[2][3]=(b123+b234+b235+b145-he/3)/2;
	b[2][4]=(b124+b234+b245+b135-he/3)/2;
	b[2][5]=(b125+b235+b245+b134-he/3)/2;
	b[3][4]=(b134+b234+b345+b125-he/3)/2;
	b[3][5]=(b135+b235+b345+b124-he/3)/2;
	b[4][5]=(b145+b245+b345+b123-he/3)/2;
	int mx=-1,x=0,y=0,z=0;
	for(int i=1;i<5;++i)for(int j=i+1;j<=5;++j){
		if(b[i][j]>mx)mx=b[i][j],x=i,y=j;
	}
	mx=-1;
	for(int i=1;i<=5;++i)if(i!=x&&i!=y){
		int d1=(x<i?b[x][i]:b[i][x]),d2=(y<i?b[y][i]:b[i][y]);
		if(d1+d2>mx)mx=d1+d2,z=i;
	}
	if(x>y)swap(x,y);
	if(x>z)swap(x,z);
	if(y>z)swap(y,z);
	int dxy=b[x][y],dxz=b[x][z],dyz=b[y][z];
	for(int i=6;i<=n;++i){
		int qxy=query(x,y,i),qxz=query(x,z,i),qyz=query(y,z,i);
		int he=(qxy-dxy+qxz-dxz+qyz-dyz)/2;
		d[0][1]=dxy,d[0][2]=dxz,d[1][2]=dyz;
		d[0][3]=he-qyz+dyz,d[1][3]=he-qxz+dxz,d[2][3]=he-qxy+dxy;
		p[0]=x,p[1]=y,p[2]=z,p[3]=i;
		int mx=-1;x=-1,y=-1,z=-1;
		for(int j=0;j<4;++j)for(int k=j+1;k<4;++k){
			if(mx<d[j][k])mx=d[j][k],x=j,y=k;
		}
		mx=-1;
		for(int j=0;j<4;++j)if(j!=x&&j!=y){
			int di=d[min(j,x)][max(j,x)]+d[min(j,y)][max(j,y)];
			if(di>mx)mx=di,z=j;
		}
		dxy=d[x][y],dxz=d[x][z],dyz=d[y][z];
		x=p[x],y=p[y],z=p[z];
	}
	int mn=max(max(dxy,dxz),dyz);
	if(dxy==mn)return make_pair(x,y);
	if(dxz==mn)return make_pair(x,z);
	return make_pair(y,z);
}