#include "diameter.h"
#include<bits/stdc++.h>

using namespace std;
long long yi[10][10]={
{2,2,-1,-1,2,-1,-1,-1,-1,2},
{2,-1,2,-1,-1,2,-1,-1,2,-1},
{2,-1,-1,2,-1,-1,2,2,-1,-1},
{-1,2,2,-1,-1,-1,2,2,-1,-1},
{-1,2,-1,2,-1,2,-1,-1,2,-1},
{-1,-1,2,2,2,-1,-1,-1,-1,2},
{-1,-1,-1,2,2,2,-1,2,-1,-1},
{-1,-1,2,-1,2,-1,2,-1,2,-1},
{-1,2,-1,-1,-1,2,2,-1,-1,2},
{2,-1,-1,-1,-1,-1,-1,2,2,2},
};
long long vis[5],dian[10],x[10],y[10],mu,zhi1,zhi2,op,mx;
std::pair<int, int> find_diameter(int subid, int n){
	if(n==2){
		return {1,2};
	}
	if(n==3){
		if(in(1,2,3)){
			return {2,3};
		}
		else if(in(2,1,3)){
			return {1,3};
		}
		else{
			return {1,2};
		}
	}
	if(n==4){
		vis[1]=1;
		vis[2]=1;
		vis[3]=1;
		vis[4]=1;
		if(query(1,2,3)==6){
			vis[4]=0;
		}
		if(query(1,2,4)==6){
			vis[3]=0;
		}
		if(query(1,3,4)==6){
			vis[2]=0;
		}
		if(query(2,3,4)==6){
			vis[1]=0;
		}
		if(vis[1]&&vis[2]){
			return {1,2};
		}
		if(vis[1]&&vis[3]){
			return {1,3};
		}
		if(vis[1]&&vis[4]){
			return {1,4};
		}
		if(vis[2]&&vis[3]){
			return {2,3};
		}
		if(vis[2]&&vis[4]){
			return {2,4};
		}
		if(vis[3]&&vis[4]){
			return {3,4};
		}
	}
	mu=5;
	dian[1]=1;
	dian[2]=2;
	dian[3]=3;
	dian[4]=4;
	dian[5]=5;
	op=0;
	y[0]=query(dian[1],dian[2],dian[3]);
	y[1]=query(dian[1],dian[2],dian[4]);
	y[2]=query(dian[1],dian[2],dian[5]);
	y[3]=query(dian[1],dian[3],dian[4]);
	y[4]=query(dian[1],dian[3],dian[5]);
	y[5]=query(dian[1],dian[4],dian[5]);
	y[6]=query(dian[2],dian[3],dian[4]);
	y[7]=query(dian[2],dian[3],dian[5]);
	y[8]=query(dian[2],dian[4],dian[5]);
	y[9]=query(dian[3],dian[4],dian[5]);
	for(int i=0;i<=9;i++){
		x[i]=0;
		for(int j=0;j<=9;j++){
			x[i]=x[i]+yi[j][i]*y[j];
		}
		x[i]/=6;
	}
	mx=0;
	if(x[0]>mx){
		mx=x[0];
		zhi1=dian[1];
		zhi2=dian[2];
	}
	if(x[1]>mx){
		mx=x[1];
		zhi1=dian[1];
		zhi2=dian[3];
	}
	if(x[2]>mx){
		mx=x[2];
		zhi1=dian[1];
		zhi2=dian[4];
	}
	if(x[3]>mx){
		mx=x[3];
		zhi1=dian[1];
		zhi2=dian[5];
	}
	if(x[4]>mx){
		mx=x[4];
		zhi1=dian[2];
		zhi2=dian[3];
	}
	if(x[5]>mx){
		mx=x[5];
		zhi1=dian[2];
		zhi2=dian[4];
	}
	if(x[6]>mx){
		mx=x[6];
		zhi1=dian[2];
		zhi2=dian[5];
	}
	if(x[7]>mx){
		mx=x[7];
		zhi1=dian[3];
		zhi2=dian[4];
	}
	if(x[8]>mx){
		mx=x[8];
		zhi1=dian[3];
		zhi2=dian[5];
	}
	if(x[9]>mx){
		mx=x[9];
		zhi1=dian[4];
		zhi2=dian[5];
	}
	op=1;
	while(mu<n){
		mu+=3;
		dian[1]=zhi1;
		dian[2]=zhi2;
		x[0]=mx;
		dian[3]=mu-2;
		dian[4]=mu-1;
		dian[5]=mu;
		while(dian[5]>n||dian[5]==dian[1]||dian[5]==dian[2]||dian[5]==dian[3]||dian[5]==dian[4]){
			dian[5]=rand()*998244353ll%n+1;
		}
		while(dian[4]>n||dian[4]==dian[1]||dian[4]==dian[2]||dian[4]==dian[3]||dian[4]==dian[5]){
			dian[4]=rand()*998244353ll%n+1;
		}
		y[1]=query(dian[1],dian[2],dian[4]);
		y[2]=query(dian[1],dian[2],dian[5]);
		y[3]=query(dian[1],dian[3],dian[4]);
		y[4]=query(dian[1],dian[3],dian[5]);
		y[5]=query(dian[1],dian[4],dian[5]);
		y[6]=query(dian[2],dian[3],dian[4]);
		y[7]=query(dian[2],dian[3],dian[5]);
		y[8]=query(dian[2],dian[4],dian[5]);
		y[9]=query(dian[3],dian[4],dian[5]);
		y[0]=3*x[0]-y[1]-y[2]-y[9]+(y[3]+y[4]+y[5]+y[6]+y[7]+y[8])/2;
		for(int i=0;i<=9;i++){
			x[i]=0;
			for(int j=0;j<=9;j++){
				x[i]=x[i]+yi[j][i]*y[j];
			}
			x[i]/=6;
		}
		mx=0;
		if(x[0]>mx){
			mx=x[0];
			zhi1=dian[1];
			zhi2=dian[2];
		}
		if(x[1]>mx){
			mx=x[1];
			zhi1=dian[1];
			zhi2=dian[3];
		}
		if(x[2]>mx){
			mx=x[2];
			zhi1=dian[1];
			zhi2=dian[4];
		}
		if(x[3]>mx){
			mx=x[3];
			zhi1=dian[1];
			zhi2=dian[5];
		}
		if(x[4]>mx){
			mx=x[4];
			zhi1=dian[2];
			zhi2=dian[3];
		}
		if(x[5]>mx){
			mx=x[5];
			zhi1=dian[2];
			zhi2=dian[4];
		}
		if(x[6]>mx){
			mx=x[6];
			zhi1=dian[2];
			zhi2=dian[5];
		}
		if(x[7]>mx){
			mx=x[7];
			zhi1=dian[3];
			zhi2=dian[4];
		}
		if(x[8]>mx){
			mx=x[8];
			zhi1=dian[3];
			zhi2=dian[5];
		}
		if(x[9]>mx){
			mx=x[9];
			zhi1=dian[4];
			zhi2=dian[5];
		}
	}
	return {zhi1,zhi2};
}