#include "insects.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <variant>
#include <map>
#include <random>
#include <chrono>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randint(int l, int r) {return uniform_int_distribution<int>(l, r)(rng);}
struct DisjointSetUnion {
int n;
vector<int> fa, sz;
DisjointSetUnion(int _n) : n(_n), fa(n), sz(n, 1) {iota(fa.begin(), fa.end(), 0);}
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int size(int x) {
return sz[find(x)];
}
bool same(int x, int y) {
return find(x) == find(y);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
fa[y] = x;
sz[x] += sz[y];
}
};
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N) {
int n = N;
vector<int> p(n);
iota(p.begin(), p.end(), 0);
shuffle(p.begin(), p.end(), rng);
DisjointSetUnion dsu(n);
vector<int> v;
for (int x: p) {
bool uni = true;
move_inside(x);
for (int y: v) {
move_inside(y);
bool sm = press_button() == 2;
move_outside(y);
if (sm) {dsu.merge(x, y); uni = false; break;}
}
move_outside(x);
if (uni) v.push_back(x);
}
int ans = n;
for (int x: v) ans = min(ans, dsu.size(x));
return ans;
}
