#include "insects.h"
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#ifdef DEBUG
auto& operator<<(auto& os, pair<auto, auto> &p) {
return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto& os, const auto &v) {
os<<"{";
for(auto it=begin(v);it!=end(v);++it) {
if(it != begin(v)) os<<", ";
os<<(*it);
}
return os<<"}";
}
void dbg_out(auto... x) {
((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif
int n;
vi perm;
vector<bool> added;
void in(int i) {
if(added[i]) return;
added[i] = true;
move_inside(perm[i]);
}
void out(int i) {
if(!added[i]) return;
added[i] = false;
move_outside(perm[i]);
}
vi siz;
vi ind;
void find(int index) {
dbg(index);
in(index);
for(auto x : ind)
in(x);
if(press_button() == 1) {
siz[index] = 1;
ind.push_back(index);
return;
}
int b = 0, e = sz(ind)-1;
while(b < e) {
int mid = (b + e + 1) / 2;
rep(i,b,mid) in(ind[i]);
rep(i,mid,e+1) out(ind[i]);
dbg(b, e, mid);
if(press_button() == 1)
b = mid;
else
e = mid - 1;
}
dbg(ind[b]);
siz[ind[b]]++;
out(index);
}
int min_cardinality(int N) {
n = N;
perm.resize(n);
iota(all(perm), 0);
random_shuffle(all(perm));
added.assign(n, 0);
siz.assign(n, -1);
siz[0] = 1;
ind.push_back(0);
rep(i,1,n) find(i);
dbg(siz);
dbg(ind);
int mini = n;
rep(i,0,n)
if(siz[i] != -1)
mini = min(mini, siz[i]);
return mini;
}
