#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define pb push_back
#define ll long long
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int nax=5005;
int parent[nax];
int sz[nax];
int find(int x){
if(parent[x]==x) return x;
return parent[x]=find(parent[x]);
}
bool sameset(int x,int y){
return find(x)==find(y);
}
void joinset(int x,int y){
x=find(x);
y=find(y);
parent[x]=y;
sz[y]+=sz[x];
return;
}
int min_cardinality(int N) {
vector<pair<int,int>> tab;
for (int i = 0; i < N; ++i)
{
parent[i]=i;
sz[i]=1;
}
for (int i = 0; i < N; ++i)
{
for (int j = i+1; j < N; ++j)
{
tab.pb({i,j});
}
}
int cnt=0;
shuffle(tab.begin(),tab.end(),rng);
for (int i = 0; i < min(N*(N-1)/2,20000); ++i)
{
if(sameset(tab[i].fi,tab[i].se)) continue;
cnt++;
move_inside(tab[i].fi);
move_inside(tab[i].se);
int a=press_button();
move_outside(tab[i].fi);
move_outside(tab[i].se);
if(a==2) joinset(tab[i].fi,tab[i].se);
}
int mn=1e9;
for (int i = 0; i < N; ++i)
{
mn=min(mn,sz[find(i)]);
}
return mn;
}
