#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
int n = N;
// test every pair of insects and check if they share a type
// if a == b and a == c, then c == b
vector<vector<bool>> matches(n, vector<bool>(n));
vector<int> groups(n);
int group_id = n;
for(int i = 0; i < n; i++) groups[i] = i;
for(int i = 0; i < n; i++){
move_inside(i);
// cout << "chekcing ppl against " << i << "\n";
for(int j = i + 1; j < n; j++){
move_inside(j);
if(press_button() == 2){
// cout << "matches " << j << "\n";
matches[i][j] = true;
}
move_outside(j);
}
move_outside(i);
}
// count up groups
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(matches[i][j]){
if(groups[i] != groups[j]){
int old_j = groups[j];
for(int k = 0; k < n; k++){
if(groups[k] == old_j) groups[k] = groups[i];
}
}
}
}
}
map<int, int> freq;
for(auto i : groups) freq[i]++;
int res = INT_MAX;
for(auto i : freq) res = min(res, i.second);
return res;
}
