#include "insects.h" #include <bits/stdc++.h> using std::cin; using std::cout; using std::endl; using std::vector; using std::string; using ll = long long; using vi = vector<ll>; using vii = vector<vi>; using pii = std::pair<ll,ll>; constexpr ll mod = 1'000'002'022; #define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++) #define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++) #define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--) #define all(a) a.begin(),a.end() #define pb emplace_back #define ln "\n" struct union_find{ int N; vi par; union_find(int n): N(n){ par.resize(N); rep(i,0,N) par[i] = i; } ll root(ll u){ if(par[u] == u) return u; return par[u] = root(par[u]); } void merge(ll u, ll v){ u = root(u); v = root(v); if(u != v){ par[u] = v; } } }; int min_cardinality(int N) { union_find tree(N); std::function<vi(ll,ll)> dfs = [&](ll l, ll r){ if(l+1 == r){ vi ret = {l}; return ret; } ll m = (l+r)/2; vi L = dfs(l,m), R = dfs(m,r); std::set<ll> nex; { vi nL, nR; rep(i,0,L.size()) move_inside(L[i]); rep(i,0,R.size()){ move_inside(R[i]); if(press_button() == 1){ nex.insert(R[i]); } else{ nR.pb(R[i]); } move_outside(R[i]); } rep(i,0,L.size()) move_outside(L[i]); rep(i,0,R.size()) move_inside(R[i]); rep(i,0,L.size()){ move_inside(L[i]); if(press_button() == 1){ nex.insert(L[i]); } else{ nL.pb(L[i]); } move_outside(L[i]); } rep(i,0,R.size()) move_outside(R[i]); L = nL; R = nR; assert(L.size() == R.size()); } if(L.size() > R.size()) std::swap(L,R); ll sz = R.size(); vi flag(sz); rep(i,0,sz){ move_inside(L[i]); rep(j,0,sz){ if(flag[j]) continue; move_inside(R[j]); if(press_button() == 2){ flag[j] = true; tree.merge(L[i], R[j]); move_outside(R[j]); break; } move_outside(R[j]); } move_outside(L[i]); } for(auto el: L) nex.insert(el); vi ret(all(nex)); /*cout << l << " " << r << " "; for(auto el: L) cout << el << " "; cout << " "; for(auto el: R) cout << el << " "; cout << " "; rep(i,0,sz) cout << left[i] << " "; cout << " "; for(auto el: ret) cout << el << " "; cout << endl;*/ return ret; }; dfs(0,N); vi cnt(N); //rep(i,0,N) cout << tree.root(i) << endl; rep(i,0,N) cnt[tree.root(i)]++; ll min = N; rep(i,0,N){ if(cnt[i]) min = std::min(min, cnt[i]); } return int(min); }