#include"diameter.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
const int N=100009;
int n,vis[N],dis[N];
vector<int> bel;
void clr(){
	for(int i=0;i<=n;i++) vis[i]=dis[i]=0;
	bel.clear();
	return;
}
pii find_diameter(int testid,int nn){
	n=nn;
	if(n==1) return mp(1,1);
	if(n==2) return mp(1,2);
	int mn=n+1,len;
	for(int i=3;i<=n;i++){
		len=query(1,2,i)/2;
		if(len<mn){
			mn=len;
			bel.clear();
		}
		if(len==mn)
			bel.push_back(i);
	}
	len=mn;
	int u,v,nd1,nd2,l;
	if(len==2){
		if(in(bel[0],1,2)) nd1=1,nd2=bel[0];
		else nd1=1,nd2=2;
	}
	else{
		u=bel[0]; v=bel[1];
		l=(query(1,2,u)+query(1,2,v)-len*2)/2;
		if(l==len-2){
			if(in(u,v,1)) nd1=1,nd2=u;
			else nd1=1,nd2=v;
		}
		else{
			for(int i=2;i<bel.size();i++){
				len=query(u,v,bel[i])/2;
				if(len==l+1){
					if(in(u,v,bel[i])) nd1=u,nd2=bel[i];
					else nd1=v,nd2=bel[i];
					break;
				}
			}
		}
		for(int i=0;i<bel.size();i++)
			vis[bel[i]]=1;
	}
	vis[nd1]=vis[nd2]=1;
	int ans,ans1,ans2,mx=-1;
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		dis[i]=query(nd1,nd2,i)/2-1;
		if(dis[i]>mx){
			mx=dis[i];
			ans1=i;
		}
	}
	vis[ans1]=1;
	int rt,x;
	if(in(nd1,ans1,nd2)) rt=nd1;
	else rt=nd2;
	ans2=(nd1^nd2^rt); ans=mx+1;
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		len=query(ans1,rt,i)/2;
		if(len!=mx+dis[i]+1){
			x=mx+dis[i]-len;
			len-=x;
		}
		if(len>ans){
			ans=len;
			ans2=i;
		}
	}
	clr();
	return mp(ans1,ans2);
}