#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
int n = N;
vector<int> in(n);
vector<int> roots;
for (int i = 0; i < n; i++) {
move_inside(i);
if (press_button() == 2) {
move_outside(i);
} else {
roots.push_back(i);
in[i] = true;
}
}
assert((int) roots.size() > 0);
for (int i = 0; i < (int) roots.size(); i++) {
move_outside(roots[i]);
}
if ((int) roots.size() < n / (int) roots.size()) {
int res = 1234567;
for (int it = 0; it < (int) roots.size(); it++) {
move_inside(roots[it]);
int cnt = 1;
for (int j = 0; j < n; j++) {
if (j == roots[it]) {
continue;
}
move_inside(j);
if (press_button() == 2) {
cnt++;
}
move_outside(j);
}
res = min(res, cnt);
move_outside(roots[it]);
}
return res;
} else {
vector<int> cur_roots(roots.begin(), roots.end());
int len = 0;
while ((int) cur_roots.size() == (int) roots.size()) {
++len;
cur_roots.clear();
for (int i = 0; i < n; i++) {
if (in[i]) {
continue;
}
move_inside(i);
if (press_button() == 2) {
move_outside(i);
} else {
cur_roots.push_back(i);
in[i] = true;
}
}
}
return len;
}
return 0;
}
