#include "diameter.h"
#include <bits/stdc++.h>
#define int long long 
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int INF=105;
const int Mod=998244353;
int ksm(int x,int y) {
	int ba=x%Mod,ans=1;
	while (y) {
		if (y&1) ans=(ans*ba)%Mod;
		ba=(ba*ba)%Mod;y>>=1;
	}
	return ans;
}
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() {
	memset(g,0,sizeof g);
	int tot2=0; tot1=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++) {
		int la=i;
		for (int j=i+1;j<=tot1;j++) 
			if (g[j][i]) la=j;
		swap(g[i],g[la]);
		int t=ksm(g[i][i],Mod-2);
//		cerr<<t<<" "<<g[i][i]<<" bomb233\n";
		for (int j=1;j<=tot1+1;j++) g[i][j]*=t,g[i][j]%=Mod;
		for (int j=i+1;j<=tot1;j++) {
			int tt=g[j][i];
			for (int k=1;k<=tot1+1;k++)
				g[j][k]-=tt*g[i][k],g[j][k]%=Mod;
		}
//		for (int x=1;x<=tot1;x++) {
//			for (int y=1;y<=tot1+1;y++)
//				cerr<<g[x][y]<<" ";
//			cerr<<" endl233\n";	
//		}
//		cerr<<" print!\n";
	}
	
	for (int i=tot1;i;i--) {
		g[i][tot1+1]*=ksm(g[i][i],Mod-2);g[i][tot1+1]%=Mod;
		for (int j=1;j<i;j++)
			g[j][tot1+1]-=g[i][tot1+1]*g[j][i],g[j][tot1+1]%=Mod;
	}
	// g[1...tot1][tot1+1]
	for (int i=1;i<=tot1;i++) f[i]=(g[i][tot1+1]%Mod+Mod)%Mod;
	int Max=0,rt1=0,rt2=0,rt3=0;
	for (int x=1;x<=5;x++) {
		for (int y=x+1;y<=5;y++) {
//			cerr<<x<<" "<<y<<" "<<f[id[x][y]]<<" qwq?\n";
			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)/2;
		// 如果在 rt1 下面就是
//		cerr<<dd<<" "<<Max<<" "<<it3<<" qwq?\n";
		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;
		}
		// 如果两个都不在呢？
		 
		if (dd*2+Max2*2<it3) {
			// 则在 rt3 左边 
			// it3/2 
			if (it3/2>Max) {
				Max=it3/2;rt1=u;
				Max1=Max-Max2;
			}
		} else if (dd*2+Max1*2<it1) {
			// 则在 rt3 右边
			if (it1/2>Max) {
				Max=it1/2;rt2=u;
				Max2=Max-Max1;
			}
		} else {
			// 则在 rt3 下面 
			if (it3/2>Max) {
				Max=it3/2;rt1=u;
				Max1=Max-Max2;
			}
		}
	}
	return make_pair(rt1,rt2);
}
std::pair<signed, signed> find_diameter(signed subid, signed 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();
	}
}