#include "diameter.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int INF=105;
int g[INF][INF],id[INF][INF],n,tot1,tot2,f[INF];
int ff(int x,int y) {
	if (x>y) swap(x,y);
	return id[x][y];
}
pii solve() {
	int tot2=0;
	for (int x=1;x<=5;x++)
		for (int y=x+1;y<=5;y++)
			id[x][y]=++tot2;
	for (int x=1;x<=5;x++)
		for (int y=x+1;y<=5;y++)
			for (int z=y+1;z<=5;z++) {
				++tot1;
				g[tot1][id[x][y]]=1;
				g[tot1][id[x][z]]=1;
				g[tot1][id[y][z]]=1;
				g[tot1][tot2+1]=query(x,y,z);
			}
//	for (int i=1;i<=tot1;i++) {
//		for (int j=1;j<=tot1+1;j++)
//			cerr<<g[i][j]<<" ";
//		cerr<<"\n";
//	}
	for (int i=1;i<=tot1;i++) {
		int la=i;
		for (int j=i+1;j<=tot1;j++) 
			if (g[j][i]) la=j;
		swap(g[i],g[la]);
		int t=g[i][i];
		for (int j=1;j<=tot1+1;j++) g[i][j]/=t;
		for (int j=i+1;j<=tot1;j++) {
			int tt=g[j][i]/g[i][i];
			for (int k=1;k<=tot1+1;k++)
				g[j][k]-=tt*g[i][k];
		}
	}
	for (int i=tot1;i;i--) {
		g[i][tot1+1]/=g[i][i];
		for (int j=1;j<i;j++)
			g[j][tot1+1]-=g[i][tot1+1]*g[j][i];
	}
	// g[1...tot1][tot1+1]
	for (int i=1;i<=tot1;i++) f[i]=g[i][tot1+1];
	int Max=0,rt1=0,rt2=0,rt3=0;
	for (int x=1;x<=5;x++) {
		for (int y=x+1;y<=5;y++) {
			if (Max<f[id[x][y]]) {
				Max=f[id[x][y]];
//				cerr<<x<<" "<<y<<" endl233\n";
				for (int z=1;z<=5;z++) {
					if (x==z || z==y) continue;
					if (f[ff(x,z)]+f[ff(y,z)]==f[ff(x,y)])
						rt1=x,rt2=y,rt3=z;
				}
			}
		}
	}
//	cerr<<rt1<<" "<<rt2<<" "<<rt3<<" endl233\n";
	// rt1 -- rt3 --- rt2 rt1->rt2 为 Max 
	int Max1=f[ff(rt1,rt3)],Max2=f[ff(rt3,rt2)];
	for (int u=6;u<=n;u++) {
		int it1=query(rt1,rt3,u),it2=query(rt1,rt2,u),it3=query(rt2,rt3,u);
		int dd=it2-Max*2;
		// 如果在 rt1 下面就是
		if (dd*2+Max1*2==it1 && dd*2+Max*2==it3) {
			int t1=dd,t2=Max,t3=dd+Max;
			Max=t3;Max2=t2;Max1=t1;
			rt3=rt1;rt1=u;
		}
		// 如果在 rt2 下面就是
		if (dd*2+Max2*2==it3 && dd*2+Max*2==it1) {
			int t1=Max,t2=dd,t3=dd+Max;
			Max=t3;Max1=t1;Max2=t2;
			rt3=rt2;rt2=u;
		}
	}
	return make_pair(rt1,rt2);
}
std::pair<int, int> find_diameter(int subid, int N) {
	n=N;
	if (n==1) return make_pair(1,1);
	else if (n==2) return make_pair(1,2);
	else {
		if (n==3) {
			if (in(1,2,3)) return make_pair(2,3);
			else if (in(2,1,3)) return make_pair(1,3);
			else return make_pair(1,2);
		}
		if (n==4) {
			int Max=0,rt1=0,rt2=0,rt3=0;
			for (int x=1;x<=n;x++)
				for (int y=x+1;y<=n;y++)
					for (int z=y+1;z<=n;z++) {
						int kk=query(x,y,z);
						if (Max<kk) Max=kk,rt1=x,rt2=y,rt3=z;
					}
			if (in(rt1,rt2,rt3)) return {rt2,rt3};
			else if (in(rt2,rt1,rt3)) return {rt1,rt3};
			else return {rt1,rt2};
		}
		return solve();
	}
}