#include "friend.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1005;
int N,niz[maxn],par[maxn];
int prosli[maxn],pvred,boja[maxn];
bool uparen[maxn];
vector<int> koji[2];
ll res=0;
mt19937_64 rng;
bool postoji[maxn][maxn];
void grana(int a,int b){
postoji[a][b]=true;
postoji[b][a]=true;
}
void dfs(int gde,int bb){
//cout<<"NA "<<gde<<endl;
koji[bb].push_back(gde);
boja[gde]=bb;
bb^=1;
prosli[gde]=pvred;
for(int x=1;x<=N;x++){
// cout<<x<<" "<<postoji[gde][x]<<endl;
if(prosli[x]!=pvred and postoji[gde][x])
dfs(x,bb);
}
return;
}
bool upari(int x){
if(prosli[x]==pvred)
return false;
prosli[x]=pvred;
for(int i=1;i<=N;i++){
if(!postoji[i][x])
continue;
if(par[i]==0){
par[i]=x;
return true;
}
if(upari(par[i])){
par[i]=x;
return true;
}
}
return false;
}
int calcmatching(){
pvred++;
dfs(1,1);
//if(koji[0]>koji[1])
// swap(koji[0],koji[1]);
//for(int i=1;i<koji[0].size();i++)
// swap(koji[0][i],koji[0][rng()%(i+1)]);
/* for(int x:koji[0]){
for(int i=1;i<=N;i++){
if(!postoji[x][i])
continue;
if(par[i]!=0)
continue;
par[i]=x;
uparen[x]=true;
break;
}
}*/
//cout<<koji[0].size()<<" sz "<<koji[1].size()<<endl;
for(int x:koji[0]){
// cout<<"POKUSAJ "<<x<<endl;
if(uparen[x])
continue;
pvred++;
uparen[x]=upari(x);
}
int br=0;
for(int x:koji[0])
if(uparen[x])
br++;
return br;
}
int findSample(int n,int confidence[],int host[],int protocol[]){
N=n;
rng.seed(52366);
for(int i=1;i<=N;i++)
niz[i]=confidence[i-1];
for(int i=1;i<N;i++){
int x=host[i]+1;
int p=protocol[i];
if(p==1 or p==2){
for(int aa=1;aa<=i;aa++)
if(postoji[x][aa])
grana(aa,i+1);
}
if(p==0 or p==2)
grana(x,i+1);
}
return N-calcmatching();
}
