#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
// subtask 5
const int MAXN=1000;
int l=0, r=0;
int left_of[MAXN], right_of[MAXN];
bool seen[MAXN]={false}, visited[MAXN]={false};
vector<int> adj[MAXN], adjtemp[MAXN];
void dfs(int x, int t, bool parity)
{
if (visited[x])
return;
visited[x]=true;
if (parity==0)
l=l+1;
else
r=r+1;
for (auto y : adjtemp[x])
{
if (y==t)
continue;
if (parity==0)
adj[x].push_back(y);
dfs(y, x, (parity+1)%2);
}
return;
}
bool find_match(int index)
{
if (seen[index])
return false;
seen[index]=true;
for (int next : adj[index])
if (left_of[next]==-1)
{
left_of[next]=index;
right_of[index]=next;
return true;
}
for (int next : adj[index])
{
int current_connection=left_of[next];
if (find_match(current_connection))
{
left_of[next]=index;
right_of[index]=next;
return true;
}
}
return false;
}
int findSample(int n, int confidence[], int host[], int protocol[])
{
for (int i=1; i<n; i++)
{
if (protocol[i]==0)
{
adjtemp[host[i]].push_back(i);
adjtemp[i].push_back(host[i]);
}
if (protocol[i]==1)
for (auto x : adjtemp[host[i]])
{
adjtemp[x].push_back(i);
adjtemp[i].push_back(x);
}
}
for (int i=0; i<n; i++)
dfs(i, -1, 0);
for (int i=0; i<r; i++)
left_of[i]=-1;
for (int i=0; i<l; i++)
right_of[i]=-1;
int matched=0;
for (int i=0; i<l; i++)
{
for (int j=0; j<l; j++)
seen[j]=0;
if (find_match(i))
matched=matched+1;
}
return n-matched;
}
