#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;
}
