#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) (int) (x).size()
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
struct DSU {
int n;
vi par, siz;
DSU(int N) {
n = N;
par.resize(n); iota(all(par), 0);
siz.assign(n, 1);
}
int find_set(int v) {
if (par[v] == v) return v;
return par[v] = find_set(par[v]);
}
void union_set(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (siz[a] < siz[b]) swap(a, b);
par[b] = a;
siz[a] += siz[b];
}
}
};
int quadratic(int N) {
auto dsu = DSU(N);
FOR(i, 0, N) {
move_inside(i);
FOR(j, 0, N) {
// todo see if I can reduce checks where I already know that there isn't an edge between set a and set b
if(dsu.find_set(i) == dsu.find_set(j)) continue;
move_inside(j);
if (press_button() > 1) {
dsu.union_set(i, j);
}
move_outside(j);
}
move_outside(i);
}
int minsz = INT_MAX;
FOR(i, 0, N) minsz = min(minsz, dsu.siz[dsu.find_set(i)]);
return minsz;
}
int window(int N) {
auto dsu = DSU(N);
set<int> active = {0};
int cursz = 1;
move_inside(0);
FOR(i, 1, N) {
move_inside(i);
int newsz = press_button();
if (newsz > cursz) {
int toerase = -1;
for (auto &el : active) {
move_outside(el);
if (press_button() < newsz) {
dsu.union_set(i, el);
toerase = el;
break;
} else {
move_inside(el);
}
}
if (toerase != -1) active.erase(toerase);
}
active.insert(i);
}
int minsz = INT_MAX;
FOR(i, 0, N) minsz = min(minsz, dsu.siz[dsu.find_set(i)]);
return minsz;
}
int min_cardinality(int N) {
return window(N);
}
