#include "insects.h"
#include <bits/stdc++.h>
//#include "stub.cpp"
using namespace std;
typedef pair<int,int> pii;
int cul[2005];
int n;
vector<int> spec;
struct date
{
int nod,l,r;
};
vector<date> need;
bool comp(date a, date b)
{
return a.l<b.l;
}
struct ev
{
int l,r,nod,poz;
};
bool compev(ev a, ev b)
{
return a.l<b.l;
}
int f[2005];
ev v[2005][3];
int have[2005][3];
int min_cardinality(int N)
{
n=N;
cul[0]=1;
spec.push_back(0);
move_inside(0);
int nr=1;
for(int i=1;i<n;i++)
{
move_inside(i);
int cnt=press_button();
if(cnt>=2)
move_outside(i);
else
{
nr++;
cul[i]=nr;
spec.push_back(i);
}
}
if(spec.size()==1)
return n;
for(int i=0;i<n;i++)
if(cul[i]==0)
need.push_back({i,0,(int)spec.size()-1});
int l=0,r=spec.size();
r--;
while(!need.empty())
{
for(int i=l;i<=r;i++)
move_outside(spec[i]);
vector<ev> events;
for(date p:need)
{
int nod=p.nod;
int l=p.l;
int r=p.r;
have[nod][0]=0;
have[nod][1]=0;
have[nod][2]=0;
if(r-l+1==2)
{
ev a={l,l,nod,0};
ev b={r,r,nod,1};
events.push_back(a);
v[nod][0]=a;
v[nod][1]=b;
v[nod][2]={-1,-1,0,0};
}
else
{
int lg=r-l+1;
int mij1=l+lg/3-1;
int mij2=mij1+lg/3;
//assert(l<=mij1&&mij1+1<=mij2&&mij2+1<=r);
ev a={l,mij1,nod,0};
ev b={mij1+1,mij2,nod,1};
ev c={mij2+1,r,nod,2};
v[nod][0]=a;
v[nod][1]=b;
v[nod][2]=c;
events.push_back(a);
events.push_back(b);
}
}
sort(events.begin(),events.end(),compev);
l=-1;
r=-1;
for(auto p:events)
{
int nod=p.nod;
int lft=p.l;
int rgt=p.r;
if(have[nod][0]+have[nod][1]+have[nod][2]>=1)
continue;
if(l==-1)
{
l=lft;
r=rgt;
for(int i=lft;i<=rgt;i++)
move_inside(spec[i]);
}
if(lft>r)
{
for(int i=l;i<=r;i++)
move_outside(spec[i]);
l=lft;
r=rgt;
for(int i=l;i<=r;i++)
move_inside(spec[i]);
}
move_inside(nod);
int cnt=press_button();
move_outside(nod);
if(cnt>=2)
have[nod][p.poz]=1;
}
vector<date> aux;
for(date p:need)
{
int nod=p.nod;
int l=-1,r=-1;
for(int z=0;z<=2;z++)
if(have[nod][z])
{
l=v[nod][z].l;
r=v[nod][z].r;
}
if(l==-1)
{
if(v[nod][2].l==-1)
{
l=v[nod][1].l;
r=v[nod][1].r;
}
else
{
l=v[nod][2].l;
r=v[nod][2].r;
}
}
if(l==r)
cul[nod]=cul[spec[l]];
else
aux.push_back({nod,l,r});
}
need=aux;
sort(need.begin(),need.end(),comp);
}
for(int i=0;i<n;i++)
{
assert(cul[i]>0);
f[cul[i]]++;
}
int minim=1e9;
for(int i=1;i<=nr;i++)
minim=min(minim,f[i]);
return minim;
}
