#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
vector<int> mt,graph[1001],graph2[1001];
int n,k,val[1001],which[1001];
vector<bool> used;
bool try_kuhn(int v) {
assert(v < n);
if (used[v])
return false;
used[v] = true;
for (int to : graph[v]) {
assert(to < k);
if (mt[to] == -1 || try_kuhn(mt[to])) {
mt[to] = v;
return true;
}
}
return false;
}
int findSample(int N , int confidence[] , int host[] , int protocol[]){
which[0] = 0 , val[0] = 0;
n = 1 , k = 0;
for(int i = 1 ; i < N ; i += 1){
if(protocol[i] == 0){
which[i] = 1-which[host[i]];
if(which[i] == 0){
val[i] = n++;
graph[val[i]].push_back(val[host[i]]);
graph2[val[host[i]]].push_back(val[i]);
}else{
val[i] = k++;
graph[val[host[i]]].push_back(val[i]);
graph2[val[i]].push_back(val[host[i]]);
}
}else{
which[i] = which[host[i]];
if(which[i] == 0){
val[i] = n++;
for(auto j : graph[val[host[i]]]){
graph[val[i]].push_back(j);
graph2[j].push_back(val[i]);
}
}else{
val[i] = k++;
for(auto j : graph2[val[host[i]]]){
graph[j].push_back(val[i]);
graph2[val[i]].push_back(j);
}
}
}
}
mt.assign(k, -1);
for (int v = 0; v < n; ++v) {
used.assign(n, false);
try_kuhn(v);
}
int mx = 0;
for(int i = 0 ; i < k ; i += 1){
if(mt[i] != -1){
mx += 1;
}
}
return N-mx;
}
