#include "insects.h" #pragma GCC target ("avx2") #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #include<bits/stdc++.h> #include<math.h> using namespace std; typedef int ll; typedef long double ld; typedef pair<ll, ll> pl; typedef vector<ll> vl; #define FD(i, r, l) for(ll i = r; i > (l); --i) #define K first #define V second #define G(x) ll x; cin >> x; #define GD(x) ld x; cin >> x; #define GS(s) string s; cin >> s; #define EX(x) { cout << x << '\n'; exit(0); } #define A(a) (a).begin(), (a).end() #define F(i, l, r) for (ll i = l; i < (r); ++i) #define NN 2010 #define M 1000000007 // 998244353 //DSU ll parent[NN], sz[NN]; ll find(ll a){ return a == parent[a] ? a : parent[a] = find(parent[a]); } void merge(ll u, ll v) { u = find(u), v=find(v); if (u!=v) { if (sz[u]<sz[v]) swap(u, v); sz[u] += sz[v]; parent[v] = u; } } vector<pair<pl, ll>> cache; void query(ll i, ll j) { if (find(i) == find(j)) return; for (auto [hist, q]: cache) { auto [li, ri] = hist; if (find(li) == find(i) and find(ri) == find(j)) { // we already know the answer for this if (q == 2) merge(i, j); return; } } // assume I is already moved in move_inside(j); ll shit = press_button(); if (shit == 2) merge(i, j); cache.emplace_back(pair(i, j), shit); move_outside(j); } void rec(ll l, ll r) { if (l + 1 >= r) return; ll m = (l+r)/2; rec(l, m); rec(m, r); F(i, l, m) { move_inside(i); F(j, m, r) { query(i, j); } move_outside(i); } } int min_cardinality(int N) { F(i, 0, N) parent[i] = i, sz[i] = 1; rec(0, N); ll ans = N; F(i, 0, N) ans = min(ans, sz[find(i)]); return ans; }