#include<bits/stdc++.h>
#include "diameter.h"
using namespace std;
const int MAXN=1e5+5;
int f[MAXN],g1[MAXN],g2[MAXN];
int d1[MAXN],d2[MAXN],dx[MAXN];
pair<int,int> find_diameter(int task_id,int n) {
	if(n==1) return {1,1};
	if(n==2) return {1,2};
	for(int i=3;i<=n;++i) f[i]=query(1,2,i);
	int u=min_element(f+3,f+n+1)-f;
	if(f[u]==4) f[0]=in(u,1,2)?2:1;
	else f[0]=f[u]/2;
	d1[2]=d2[1]=f[0];
	int x=max_element(f+3,f+n+1)-f;
	for(int i=3;i<=n;++i) if(i!=x) {
		g1[i]=query(1,x,i);
		g2[i]=query(2,x,i);
	}
	g1[1]=g1[x]=n+1,g1[2]=f[x],u=min_element(g1+1,g1+n+1)-g1;
	if(g1[u]==4) g1[0]=in(u,1,x)?2:1;
	else g1[0]=g1[u]/2;
	d1[x]=dx[1]=g1[0];
	d2[x]=dx[2]=g2[0]=f[x]-g1[0]-f[0];
	for(int i=3;i<=n;++i) if(i!=x) {
		int a=f[i]-f[0],b=g1[i]-g1[0],c=g2[i]-g2[0],s=(a+b+c)/2;
		dx[i]=s-a,d2[i]=s-b,d1[i]=s-c;
	}
	int a=max_element(d1+1,d1+n+1)-d1;
	int b=max_element(d2+1,d2+n+1)-d2;
	int c=max_element(dx+1,dx+n+1)-dx;
	return {a,b+c-a};
}