#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++)
const int mxN = 32;
v<int> gr;
int case1(int N) {
map<int, int> mp;
for (auto x : gr) {
move_outside(x);
mp[x] = 1;
}
int ans = 1e9;
for (auto x : gr) {
int cmp = 1;
move_inside(x);
rep(i, 0, N) {
if (mp.count(i) || i == x) continue;
move_inside(i);
int a = press_button();
if (a == 2) {
cmp++;
}
move_outside(i);
}
move_outside(x);
ans = min(ans, cmp);
}
return ans;
}
int min_cardinality(int N) {
map<int, int> mp;
int in = 0;
int d;
rep(b, 1, N) {
rep(i, 0, N) {
if (mp.count(i)) continue;
move_inside(i);
in++;
int a = press_button();
if (a > b) {
move_outside(i);
in--;
}
else {
mp[i] = 1;
}
if (a == b && b == 1) {
gr.push_back(i);
}
}
if (b == 1) d = in;
if (d <= mxN) {
return case1(N);
}
if (in < b*d) return b-1;
}
return N;
}
