#include "diameter.h"
#include<bits/stdc++.h>
#define fst first
#define scd second
#define SZ(s) ((int)s.size())
#define all(s) s.begin(),s.end()
#define eb emplace_back
const int N=1e6+5;
using namespace std;
typedef pair<int,int> pii;
template<class T,class I> inline bool chkmax(T &a,I b){return b>a?a=b,1:0;}
template<class T,class I> inline bool chkmin(T &a,I b){return b<a?a=b,1:0;}
bool vis[N];
std::pair<int, int> find_diameter(int task_id, int n){
	if(n<=2) return pii(1,n);
	for(int i=1;i<=n;++i) vis[i]=0;
	vector<int> dis(n+1);
	int mn=1e9;
	for(int i=2;i<n;++i){
		dis[i]=query(1,i,n);
		chkmin(mn,dis[i]);
	}
	vector<int> chain;
	chain.eb(1);
	for(int i=2;i<n;++i){
		if(dis[i]==mn) chain.eb(i);
	}
	chain.eb(n);
	if(SZ(chain)==n) return pii(1,n); 
	int u=0,v=0;
	if(!in(chain[1],1,n)){
		u=n,v=1;
	}else{
		for(int i=2;i<n;++i){
			if(dis[i]==mn+2){
				u=i;
				break;
			}
		}
		mn=1e9;
		vector<int> rdis(n+1);
		for(int v:chain){
			rdis[v]=query(1,v,u);
			chkmin(mn,rdis[v]);
		}
		vector<int> black;
		for(int v:chain){
			if(rdis[v]==mn) black.eb(v),vis[v]=1;
		}
		vis[1]=vis[n]=0;
		pii res(1,0);
		for(int i=1;i<SZ(black);++i){
			int v=black[i],len=query(1,res.fst,v);
			if(len!=res.scd) res=pii(v,len);
		}
		v=res.fst;
		vis[u]=vis[v]=1;
	}
	vector<int> D(n+1);
	pii Lpoint(0,0);
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			D[i]=query(u,v,i);
			if(D[i]==dis[i]-mn) D[i]=(D[i]-2)/2;
			else D[i]/=2;
			chkmax(Lpoint,pii(D[i],i));
		}
	}
	D[v]=1,vis[v]=0;
	pii Rpoint(0,0);
	vis[Lpoint.scd]=1;
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			int x=query(u,Lpoint.fst,i)-D[Lpoint.fst]-D[i];
			chkmax(Rpoint,pii(x,i));
		}
	}
	chkmax(Rpoint,pii(D[Lpoint.scd],u));
	return pii(Lpoint.scd,Rpoint.scd);
}