#include "diameter.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
mt19937 g(time(0));
pii find_diameter(int id,int n){
  if(n==1)return make_pair(1,1);
  if(n==2)return make_pair(1,2);
  vector<int> p(n);
  iota(p.begin(),p.end(),1);
  shuffle(p.begin(),p.end(),g);
  uniform_int_distribution<> U(1,n);
  int u=U(g),v=U(g),w=U(g);
  while(v==u)v=U(g);
  while(w==u||w==v)w=U(g);
  int c=query(u,v,w);
  for(int i=0;i<(n<=50?p.size():p.size()>>2);i++)
    if(p[i]!=u&&p[i]!=v&&p[i]!=w){
      int r1=query(u,v,p[i]),r2=query(u,w,p[i]);
      if(c=min({c,r1,r2});c==r1)w=p[i];
      else if(c==r2)v=p[i];
    }
  if(in(u,w,v))swap(u,w);
  u=c=0;
  for(int i=1;i<=n;i++)
    if(i!=v&&i!=w){
      int r=query(v,w,i);
      if(r>c)c=r,u=i;
    }
  v=U(g),w=U(g);
  while(v==u)v=U(g);
  while(w==u||w==v)w=U(g);
  c=query(u,v,w);
  for(int i=0;i<(n<=50?p.size():p.size()>>2);i++)
    if(p[i]!=u&&p[i]!=v&&p[i]!=w){
      int r1=query(u,v,p[i]),r2=query(u,w,p[i]);
      if(c=min({c,r1,r2});c==r1)w=p[i];
      else if(c==r2)v=p[i];
    }
  if(in(w,u,v))swap(w,v);
  w=c=0;
  for(int i=1;i<=n;i++)
    if(i!=u&&i!=v){
      int r=query(u,v,i);
      if(r>c)c=r,w=i;
    }
  return make_pair(u,w);
}