#include "friend.h"
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
vector<int> adj[1005], g[1005];
int cl[1005], x[1005], y[1005], d[1005];
int N;
void pfs(int u) {
for (int v : adj[u])
if (cl[v] == -1) {
cl[v] = 1-cl[u];
pfs(v);
}
}
int bfs() {
queue<int> q;
for (int u = 1; u <= N; u++)
if (x[u] == 0) {
q.push(u);
d[u] = 0;
} else d[u] = INT_MAX;
d[0] = INT_MAX;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u])
if (d[y[v]] == INT_MAX) {
d[y[v]] = d[u] + 1;
if (y[v]) q.push(y[v]);
}
}
return d[0] != INT_MAX;
}
int dfs(int u) {
if (u == 0) return 1;
for (int v : adj[u])
if (d[y[v]] == d[u] + 1)
if (dfs(y[v])) {
x[u] = v;
y[v] = u;
d[u] = INT_MAX;
return 1;
}
d[u] = INT_MAX;
return 0;
}
int maxmatch() {
int ans = 0;
while (bfs()) {
for (int u = 1; u <= N; u++)
if (x[u] == 0) if (dfs(u)) ++ans;
}
return ans;
}
int findSample(int n, int confidence[], int host[], int protocol[]){
N = n;
for (int i = 0; i < n; i++) {
adj[i].clear();
g[i].clear();
cl[i] = -1;
x[i] = y[i] = 0;
}
for (int i = 1; i < n; i++)
if (protocol[i] == 1) {
for (int v : adj[host[i]]) {
adj[v].emplace_back(i);
adj[i].emplace_back(v);
}
} else {
adj[host[i]].emplace_back(i);
adj[i].emplace_back(host[i]);
}
for (int i = 0; i < n; i++)
if (cl[i] == -1) {
cl[i] = 0;
pfs(i);
}
for (int i = 0; i < n; i++)
if (cl[i] == 0)
for (int j : adj[i]) g[i].emplace_back(j);
return n-maxmatch();
}
/*
6
1 1 1 1 1 1
0 0
0 1
1 0
2 1
0 0
*/
//4
