#include<bits/stdc++.h>
#include "towns.h"
using namespace std;
#define ll long long
static int _N;
static int _dist[110][110];
static int _quota, _user_query;
// void _ini_query(int N, int k) {
// int ret;
// _N = N;
// for (int i = 0; i < _N; i++)
// for (int j = 0; j < _N; j++) {
// ret = scanf("%d", &_dist[i][j]);
// assert(ret == 1);
// }
// if (k == 1 || k == 3) _quota = _N * (_N - 1) / 2;
// else if (k == 2 || k == 4 || k == 6) _quota = (7 * _N + 1) / 2;
// else _quota = 5 * _N;
// _user_query = 0;
// }
// int getDistance(int i, int j) {
// _user_query++;
// if (_user_query > _quota) {
// printf("0\n");
// exit(0);
// }
// if (i < 0 || i >= _N) return 0;
// if (j < 0 || j >= _N) return 0;
// return _dist[i][j];
// }
struct DSU{
vector<ll>fa,siz;
void init(ll n){
fa.resize(n+5); siz.resize(n+5);
for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;
}
ll root(ll x){
if(fa[x]==x)return x;
return fa[x]=root(fa[x]);
}
void unite(ll u, ll v){
u=root(u); v=root(v);
if(u==v)return;
if(siz[u]<siz[v])swap(u,v);
siz[u]+=siz[v]; fa[v]=u;
}
};
bool asked[150][150];
ll dist[150][150];
int get(int i, int j){
if(i==j){
dist[i][j]=0; asked[i][j]=1;
return dist[i][j];
}
if(asked[i][j]){
return dist[i][j];
}
dist[i][j]=dist[j][i]=getDistance(i,j);
asked[i][j]=asked[j][i]=1;
return dist[i][j];
}
int hubDistance(int N, int sub){
// getDistance(i, j)
for(int i=0;i<150;i++){
for(int j=0;j<150;j++){
asked[i][j]=0;
}
}
ll initial[150];
for(int i=0;i<N;i++){
initial[i]=get(0,i);
}
ll fur=-1,nd=-1;
for(int i=0;i<N;i++){
if(initial[i]>fur){
fur=initial[i]; nd=i;
}
}
ll dia[150];
for(int i=0;i<N;i++){
dia[i]=get(nd,i);
}
ll fur2=-1,nd2=-1;
for(int i=0;i<N;i++){
if(dia[i]>fur2){
fur2=dia[i]; nd2=i;
}
}
// nd,nd2 forms the diameter
// how far away from nd
ll dep[155];
dep[nd]=0; dep[nd2]=0;
ll diameter=get(nd,nd2);
dep[0]=get(0,nd)+get(0,nd2)-diameter;
dep[0]/=2;
ll fromnd=get(0,nd)-dep[0];
ll fromnd2=get(0,nd2)-dep[0];
for(int i=1;i<N;i++){
ll diff=get(0,i)+get(i,nd)-get(0,nd);
ll req=(diff+2*fromnd);
if(req==2*get(nd,i)){
// closer to nd2
dep[i]=(get(nd2,i)+get(nd,i)-diameter)/2;
}
else{
ll tryy=diff/2;
ll chn=get(i,nd)-tryy;
if(chn>fromnd){
chn=get(0,nd)-dep[0];
dep[i]=get(i,nd)-chn;
}
else{
dep[i]=tryy;
}
}
// dep[i]=(get(nd2,i)+get(nd,i)-diameter)/2;
}
vector<ll>dists;
for(int i=0;i<N;i++){
dists.push_back(get(nd,i)-dep[i]);
}
sort(dists.begin(),dists.end());
dists.erase(unique(dists.begin(),dists.end()),dists.end());
ll ans=1e18; vector<ll>cand;
for(int i=0;i<dists.size();i++){
ll val=max(dists[i],diameter-dists[i]);
if(val<ans){
cand.clear();
ans=val;
cand.push_back(dists[i]);
}
else if(val==ans){
cand.push_back(dists[i]);
}
}
bool ok=0;
for(auto& u: cand){
ll cnt=0;
for(int i=0;i<N;i++){
if(dists[i]==u){
cnt++;
}
}
ll smol=0,lar=0;
if(cnt<=N/2){
// no checking
for(int i=0;i<N;i++){
if(dists[i]<u)smol++;
else if(dists[i]>u)lar++;
}
if(smol<=N/2&&lar<=N/2)ok=1;
}
else{
// since cnt > N/2 others <= N/2
vector<ll>req;
req.push_back(0);
for(int i=0;i<N;i++){
if(dists[i]==u)req.push_back(i);
}
DSU d;
d.init(req.size());
bool used[req.size()+5];
for(int i=0;i<req.size()+5;i++)used[i]=0;
ll ptrl=1,ptrr=1;
while(ptrr<req.size()){
if(ptrl==ptrr){ptrr++; continue;}
if(used[ptrr]){ptrr++; continue;}
if(used[ptrl]){ptrl++; continue;}
ll dt=get(req[ptrl],req[ptrr]);
ll real=dep[req[ptrl]]+dep[req[ptrr]];
if(real==dt){
used[ptrl]=used[ptrr]=1; ptrl++; ptrr++;
}
else{
d.unite(ptrl,ptrr); ptrr++;
}
}
ll id=-1;
vector<ll>alll;
for(int i=1;i<req.size();i++){
if(!used[i]){
alll.push_back(i);
}
}
if(alll.size()==0){
ok=1;
}
else{
for(int i=0;i<alll.size()-1;i++){
assert(d.root(alll[i])==d.root(alll[i+1]));
}
}
for(int i=1;i<req.size();i++){
if(d.root(i)!=d.root(id)&&d.root(i)==i){
ll dt=get(req[i],req[id]);
ll real=dep[req[id]]+dep[req[i]];
if(dt!=real){
d.unite(i,id);
}
}
}
if(d.siz[d.root(id)]<=N/2)ok=1;
}
}
if(ok)return ans;
else return -ans;
}
// int main() {
// int ncase, R, N;
// int subtask;
// int ret;
// ret = scanf("%d%d",&subtask,&ncase);
// assert(ret == 2);
// for (int i = 0; i < ncase; i++) {
// ret = scanf("%d",&N);
// assert(ret == 1);
// _ini_query(N,subtask);
// R=hubDistance(N,subtask);
// printf("%d\n",R);
// }
// return 0;
// }
