#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int min_cardinality(int n) {
vector<int> st, vis(n), a(n);
st.push_back(0);
int id = 1;
for(int i=1; i<n; i++) {
shuffle(st.begin(), st.end(), rng);
int t = -1;
move_inside(i);
for(int u : st) {
move_inside(u);
if(press_button() == 2) {
t = a[u];
move_outside(u);
break;
}
move_outside(u);
}
move_outside(i);
if(t == -1) {
a[i] = id++;
st.push_back(i);
} else {
a[i] = t;
}
}
vector<int> cnt(n);
for(int i=0; i<n; i++) cnt[a[i]]++;
int mn = n;
for(int i=0; i<n; i++)
if(cnt[i]) mn = min(mn, cnt[i]);
return mn;
}
