/* Ignut
started: 11.08.2024
now: 11.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████ ████████████████████████████████
██████████████████████████████ ██████████████████████████████
██████ ██████████████████ ██████████████████ ██████
██████ ██████████████ ██████████████ ██████
██████ ██ ████████████ ████████████ ██ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ██████ ██████
██████ ██████ ██████████ ██████████ ██████ ██████
██████ ██████ ████████ ████████ ██████ ██████
██████ ██████ ██████ ██████ ██████ ██████
██████ ████ ████ ████ ████ ██████
██████ ██████████ ████ ██████████ ██████
██████ ██ ██████ ████████ ██████ ██ ██████
██████ ██████ ████████ ██████ ██████
██████ ██ ██ ██████
██████████████████████ ████ ████ ██████████████████████
████████████████████████ ██ ██ ████████████████████████
██████████████████████████ ██████████████████████████
██████████████████████████████ ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void move_inside(int i);
void move_outside(int i);
int press_button();
struct DSU {
vector<int> p, sz;
void Init(int n) {
p.assign(n, 0);
iota(p.begin(), p.end(), 0);
sz.assign(n, 1);
}
int Get(int v) {
return p[v] == v ? v : p[v] = Get(p[v]);
}
void Unite(int u, int v) {
u = Get(u), v = Get(v);
if (u == v) return;
if (sz[u] > sz[v]) swap(u, v);
sz[v] += sz[u];
p[u] = v;
}
};
int min_cardinality(int N) {
DSU dsu; dsu.Init(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.Unite(i, j);
}
move_outside(j);
}
move_outside(i);
}
int res = N;
for (int i = 0; i < N; i ++) res = min(res, dsu.sz[dsu.Get(i)]);
return res;
}
