#include "towns.h"
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
const int MAX_N=2e2+2;
int diam;
int tov[MAX_N];
int tou[MAX_N];
bool checked[MAX_N][MAX_N];
int to0[MAX_N];
int ma[MAX_N][MAX_N];
set<int>nodes,nodes1,nodes2;
int n;
int u,v;
int q;
int parent[MAX_N];
int s[MAX_N];
int Find(int a)
{
if(parent[a]==a)return a;
return parent[a]=Find(parent[a]);
}
void Merge(int a,int b)
{
int urt=Find(a);
int vrt=Find(b);
if(urt==vrt)return;
if(s[urt]>s[vrt])swap(urt,vrt);
parent[urt]=vrt;
s[vrt]+=s[urt];
}
bool check(int a,int b)
{
int dd;
if(a>b)swap(a,b);
checked[a][b]=1;
if(ma[a][b])dd=ma[a][b];
else
{
if(q>(9*n+1)/2)while(1);
dd=getDistance(a,b);
ma[a][b]=dd;
q++;
}
if(tou[a]+tov[b]-diam==dd)return 0;
Merge(a,b);
return 1;
}
int hubDistance(int N, int sub)
{
q=0;
nodes1.clear();
nodes2.clear();
n=N;
for(int i=0;i<n;i++)
{
parent[i]=i;
s[i]=1;
to0[i]=0;
tou[i]=0;
tov[i]=0;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
checked[i][j]=0;
ma[i][j]=0;
}
}
u=0;
int far=0;
for(int i=1;i<n;i++)
{
int cur=getDistance(u,i);
ma[0][i]=cur;
q++;
to0[i]=cur;
if(cur>far)
{
far=cur;
v=i;
}
}//0->v
diam=0;
for(int i=0;i<n;i++)
{
if(i==v)continue;
int cur;
if(i==0)cur=to0[v];
else
{
q++;
cur=getDistance(i,v);
ma[min(i,v)][max(i,v)]=cur;
}
tov[i]=cur;
if(cur>diam)
{
diam=cur;
u=i;
}
}//v->u
for(int i=0;i<n;i++)
{
tou[i]=to0[i];
}//u->all
int cntneg=1,cntpos=1,cntbaseneg=0,cntbasepos=0;
int mindif=1e9;
int dis1=0,dis2=0;
for(int i=0;i<n;i++)
{
if(i==u or i==v)continue;
int x=tov[i];
int y=to0[i];
x=(x-y+tov[0])/2;
int res=min(abs((diam+1)/2-x),abs(diam/2-x));
if(res<mindif)
{
mindif=res;
dis1=x;
dis2=0;
}
else if(res==mindif)
{
dis2=x;
}
}
if(dis1>dis2)swap(dis1,dis2);
for(int i=0;i<n;i++)
{
if(i==u or i==v)continue;
int x=tov[i];
int y=to0[i];
x=(x-y+tov[0])/2;
if(x==dis1 or x==dis2)
{
if(x==dis2){cntbaseneg++;nodes1.insert(i);}
else {cntbasepos++;nodes2.insert(i);}
}
else if(x<dis2)cntneg++;
else cntpos++;
}
int R=diam-(dis1==0 ? dis2 : dis1);
if(sub==4 or sub<=2)
{
if(cntbaseneg*cntbasepos!=0)
{
if(cntneg*2>n or (cntbasepos+cntpos)*2>n or cntbaseneg*2>n)return -R;
if(cntpos*2>n or (cntbaseneg+cntneg)*2>n or cntbasepos*2>n)return -R;
return R;
}
else
{
if(cntneg*2>n or cntpos*2>n or (cntbaseneg+cntbasepos)*2>n)return -R;
return R;
}
}
if(cntneg*2>n or cntpos*2>n)return -R;
if(cntbasepos*2<=n && cntbaseneg*2<=n)return R;
if(cntbaseneg*2>n)nodes=nodes1;
else nodes=nodes2;
set<int>NO=nodes;
int overhalf=-1;
int other=-1;
while(nodes.size())
{
if(nodes.size()==2)
{
overhalf=(*(nodes.begin()));
nodes.erase(overhalf);
other=(*(nodes.begin()));
if(check(overhalf,other))
{
other=-1;
}
break;
}
if(nodes.size()==1){overhalf=(*(nodes.begin()));break;}
vector<int>nod;
set<int>nnodes;
for(int x:nodes)nod.push_back(x);
for(int i=1;i<nod.size();i+=2)
{
if(check(nod[i],nod[i-1]))nnodes.insert(nod[i]);
}
if((nod.size())%2==1)
{
int sz=nod.size();
nnodes.insert(nod[sz-1]);
}
nodes=nnodes;
}
if(overhalf==-1)return R;
int cnt=0;
for(int i:NO)
{
if(Find(i)==Find(overhalf)){cnt++;continue;}
bool no=0;
for(int r:NO)
{
if(Find(r)==Find(overhalf))
{
for(int p:NO)
{
if(Find(p)==Find(i))
{
if(checked[min(p,r)][max(p,r)])no=1;
}
if(no)break;
}
}
if(no)break;
}
if(no)continue;
if(check(i,overhalf))cnt++;
}
if(2*cnt>n)return -R;
cnt=0;
overhalf=other;
if(overhalf==-1)return R;
for(int i:NO)
{
if(Find(i)==Find(overhalf)){cnt++;continue;}
bool no=0;
for(int r:NO)
{
if(Find(r)==Find(overhalf))
{
for(int p:NO)
{
if(Find(p)==Find(i))
{
if(checked[min(p,r)][max(p,r)])no=1;
}
if(no)break;
}
}
if(no)break;
}
if(no)continue;
if(check(i,overhalf))cnt++;
}
if(2*cnt>n)return -R;
return R;
}
