#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
template <typename T>
using v = vector<T>;
using pii = pair<int, int>;
using ll = long long;
#define rep(i, k, n) for (int i = k; i < n; i++)
int min_cardinality(int N) {
random_device rd;
mt19937 gen(rd());
v<int> pool(N);
rep(i, 0, N) pool[i] = i;
int ans = 1e9;
rep(i, 0, min(40, N)) {
if (pool.size() == 0) break;
//cout << i << " " << pool.size() << endl;
int r = pool.size();
uniform_int_distribution<> dis(0, r-1);
int idx = dis(gen);
v<int> to_erase;
to_erase.push_back(idx);
idx = pool[idx];
move_inside(idx);
int cmp = 1;
for (auto x : pool) {
if (x == idx) continue;
move_inside(x);
int a = press_button();
if (a == 2) {
to_erase.push_back(x);
cmp++;
}
move_outside(x);
}
move_outside(idx);
ans = min(cmp, ans);
for (auto x : to_erase) {
//cout << x << endl;
auto it = find(pool.begin(), pool.end(), x);
if (it != pool.end()) pool.erase(it);
}
}
return ans;
}
