#include "diameter.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int d12[N],d13[N],d23[N],d1[N],d123,mn12,mn13,mn23;
pair<int, int> find_diameter(int subid, int n) {
	if(n==1) return {1,1};
	if(n==2) return {1,2};
	if(n==3){
		if(in(1,2,3)) return {2,3};
		if(in(2,1,3)) return {1,3};
		return {1,2};
	}
	d123=query(1,2,3);
	mn12=mn13=d123;
	for(int i=4;i<=n;i++){
		d12[i]=query(1,2,i);
		d13[i]=query(1,3,i);
		d23[i]=query(2,3,i);
		mn12=min(mn12,d12[i]);
		mn13=min(mn13,d13[i]);
	}
	if(mn12==4){
		for(int i=3;i<=n;i++)
			if(d12[i]==mn12){
				if(!in(i,1,2)) mn12=2;
				break;
			}
	}
	if(mn13==4){
		for(int i=2;i<=n;i++)
			if(i!=3&&d13[i]==mn13){
				if(!in(i,1,3)) mn13=2;
				break;
			}
	}
	mn12/=2;mn13/=2;
	mn23=d123-mn12-mn13;
	int mx=2;
	if(mn13>mn12) mx=3;
	d1[2]=mn12,d1[3]=mn13;
	for(int i=4;i<=n;i++){
		d1[i]=(d12[i]+d13[i]+d23[i]-mn12-mn13-mn23)/2-d23[i]+mn23;
		if(d1[i]>d1[mx]) mx=i;
	}
	int ans=d1[mx],id=1;
	d12[3]=d13[2]=d123;
	for(int i=2;i<=n;i++){
		if(i==mx) continue;
		int now=-d1[i]-d1[mx];
		if(i==2) now+=d12[mx];
		else if(i==3) now+=d13[mx];
		else if(mx==2) now+=d12[i];
		else if(mx==3) now+=d13[i];
		else now+=query(1,mx,i);
		if(now>ans) ans=now,id=i;
	}
	return {mx,id};
}