#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<vector<int>> vii;
#define pb push_back
#define sz(a) (int)(a.size())
const ll INF = 1e18;
struct flowedge{
int v,u;
ll flow = 0,cap = 0;
flowedge(int _v,int _u,ll _cap){
v = _v;
u = _u;
cap = _cap;
}
};
struct dinic{
int n,m = 0,s,t;
vector<flowedge>e;
vector<int>ptr,level;
vii adj;
void add(int v,int u,ll cap){
e.pb(flowedge(v,u,cap));
e.pb(flowedge(u,v,0));
adj[v].pb(m);
adj[u].pb(++m);
m++;
}
dinic(int _n,int _s,int _t){
n = _n;
adj.resize(n);
ptr.assign(n,0);
level.assign(n,-1);
s = _s;
t = _t;
}
void bfs(){
queue<int>q;
q.push(s);
while(!q.empty()){
int v = q.front();
q.pop();
for(int x:adj[v]){
if(e[x].cap - e[x].flow && level[e[x].u] == -1){
level[e[x].u] = level[v]+1;
q.push(e[x].u);
}
}
}
}
ll dfs(int v,ll f){
if(!f)return 0;
if(v == t)return f;
for(;ptr[v]<sz(adj[v]);ptr[v]++){
int i = adj[v][ptr[v]];
if(e[i].cap - e[i].flow && level[e[i].u] == level[v] + 1){
ll mn = dfs(e[i].u,min(f,e[i].cap - e[i].flow));
//cout<<e[i].cap - e[i].flow<<" "<<mn<<'\n';
if(!mn)continue;
e[i].flow+=mn;
e[i^1].flow-=mn;
return mn;
}
}
return 0;
}
ll flow(){
ll f = 0;
while(true){
for(int i=0;i<n;i++){
ptr[i] = 0;
level[i] = -1;
}
level[s] = 0;
bfs();
//for(int i=0;i<n;i++)cout<<level[i]<<" ";
//cout<<'\n';
if(level[t] == -1)break;
while(true){
ll x = dfs(s,INF);
if(!x)break;
f+=x;
}
}
return f;
}
};
int e[1000][1000],c[1000],N;
bool vis[1000];
bool check =1;
void dfs(int v){
vis[v] = 1;
for(int i=0;i<N;i++){
if(e[v][i] && !vis[i]){
c[i] = c[v]^1;
dfs(i);
}
if(e[v][i] && vis[i] && c[i] == c[v])check = 0;
}
}
int findSample(int n,int confidence[],int h[],int protocol[]){
N=n;
int ans = 0;
bool sub4 = 1;
for(int i=1;i<n;i++){
if(protocol[i] == 2)sub4 = 0;
}
for(int i=0;i<n;i++){
if(confidence[i] > 1)sub4 = 0;
}
if(n<=10){
vector<set<int>>adj(n);
for(int i=1;i<n;i++){
if(!protocol[i]){
adj[i].insert(h[i]);
adj[h[i]].insert(i);
}else{
for(int x:adj[h[i]]){
adj[i].insert(x);
adj[x].insert(i);
}
}
if(protocol[i] == 2){
adj[i].insert(h[i]);
adj[h[i]].insert(i);
}
}
for(int i=0;i<(1<<n);i++){
vector<int>v;
int cost = 0;
for(int j=0;j<n;j++){
if(i&(1<<j)){
v.push_back(j);
cost+=confidence[j];
}
}
for(int x:v){
for(int y:v){
if(adj[x].count(y) || adj[y].count(x))cost = 0;
}
}
ans = max(ans,cost);
}
return ans;
}
assert(sub4);
if(sub4){
for(int i=1;i<n;i++){
if(!protocol[i])e[i][h[i]] = e[h[i]][i] = 1;
else{
for(int j=0;j<n;j++){
if(e[h[i]][j])e[i][j] = e[j][i] = 1;
}
}
}
dinic d(2*n+2,2*n,2*n+1);
for(int i=0;i<n;i++){
if(!vis[i])dfs(i);
}
assert(check);
for(int i=0;i<n;i++){
if(!c[i]){
d.add(2*n,i,1);
for(int j=0;j<n;j++){
if(e[i][j])d.add(i,n+j,1);
}
}
else d.add(n+i,2*n+1,1);
}
int ans = n-d.flow();
return ans;
}
return 0;
}
