#include "diameter.h"
#include <bits/stdc++.h>
using namespace std;

pair<int, int> find_diameter(int subid, int n) {
	int x=1,y=2,z=3;
	int now=query(x,y,z);
	for(int i=1;i<=n;i++){
		if(i==x||i==y||i==z) continue;
		int len=query(i,y,z);
		if(len>now){
			x=i;
			now=len;
		}
	}
	for(int i=1;i<=n;i++){
		if(i==x||i==y||i==z) continue;
		int len=query(x,i,z);
		if(len>now){
			y=i;
			now=len;
		}
	}
	for(int i=1;i<=n;i++){
		if(i==x||i==y||i==z) continue;
		int len=query(x,y,i);
		if(len>now){
			z=i;
			now=len;
		}
	}
	if(n<=50000){
		int L=now,X=x,Y=y,Z=z;
		for(int i=1;i<=n;i++){
			if(i==x||i==y||i==z) continue;
			int len=query(i,y,z);
			if(len<now){
				x=i;
				now=len;
			}
		}
		int yz=now;
		swap(x,X);
		now=L;
		
		for(int i=1;i<=n;i++){
			if(i==x||i==y||i==z) continue;
			int len=query(x,i,z);
			if(len<now){
				y=i;
				now=len;
			}
		}
		int xz=now;
		swap(y,Y);
		now=L;
		
		for(int i=1;i<=n;i++){
			if(i==x||i==y||i==z) continue;
			int len=query(x,y,i);
			if(len<now){
				z=i;
				now=len;
			}
		}
		int xy=now;
		swap(z,Z);
		now=L;
		
		if(xy>=yz&&xy>=xz){
			z=Z;
		}
		else if(xz>=xy&&xz>=yz){
			y=Y;
		}
		else x=X;
		if(in(x,y,z)){
			return {y,z};
		}
		else if(in(y,x,z)){
			return {x,z};
		}
		return {x,y};
	}
}
/*
g++ grader.cpp diameter.cpp -o diameter -O2 -lm
*/