#include <bits/stdc++.h>
void move_inside(int i);
void move_outside(int i);
int press_button();
using namespace std;
namespace {
class dsu {
int n;
vector<int> par;
public:
dsu(int n) : n(n), par(n) {
iota(par.begin(), par.end(), 0);
}
int root(int u) { return u == par[u] ? u : par[u] = root(par[u]); }
void merge(int u, int v) {
u = root(u), v = root(v);
if (u != v) {
par[v] = u;
}
}
};
} // namespace
int min_cardinality(int N) {
dsu dsu(N);
for (int i = 0; i < N; ++i) {
move_inside(i);
for (int j = i + 1; j < N; ++j) {
move_inside(j);
if (press_button() == 2) {
dsu.merge(i, j);
}
move_outside(j);
}
move_outside(i);
}
vector<int> cnt(N), roots;
for (int i = 0; i < N; ++i) {
cnt[dsu.root(i)]++;
if (dsu.root(i) == i) {
roots.push_back(i);
}
}
int ans = cnt[roots[0]];
for (int &i : roots) {
ans = min(ans, cnt[i]);
}
return ans;
}
#ifdef MACOS_LOCAL
#include "stub.cpp"
#endif
