/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <queue>
#include "friend.h"
#define maxn 1005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
typedef long double ld;
std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;
double timePassed()
{
using namespace std::chrono;
currT = high_resolution_clock::now();
double time = duration_cast<duration<double>>(currT - startT).count();
return time * TIME_MULT;
}
vector <int> v[maxn];
bool nb[maxn][maxn];
void add(int a, int b)
{
v[a].pb(b);
v[b].pb(a);
nb[a][b] = true;
nb[b][a] = true;
}
int dp[maxn][2];
int c[maxn];
bool used[maxn];
struct max_flow
{
struct edge
{
int from , to;
int c , flow;
edge(){};
edge(int _from , int _to , int _c , int _flow = 0)
{
from = _from;
to = _to;
c = _c;
flow = _flow;
}
};
int n;
vector <vector <int>> v;
vector <int> used , to;
vector <edge> e;
void init(int _n)
{
n = _n;
e.clear();
used.resize(n + 1);
v.resize(n + 1);
to.resize(n + 1);
}
int bre;
void add_edge(int from , int to , int c)
{
v[from].pb(bre);
v[to].pb(bre + 1);
e.push_back({from , to , c});
e.push_back({to , from , 0});
bre += 2;
}
queue <int> q;
bool bfs(int start , int endd)
{
for(int i = 0; i <= n; i++)
used[i] = -1;
used[start] = 0;
q.push(start);
int node;
while(q.size() != 0)
{
node = q.front();
q.pop();
for(int idx : v[node])
if(used[e[idx].to] == -1 && e[idx].c > e[idx].flow)
{
q.push(e[idx].to);
used[e[idx].to] = used[node] + 1;
}
}
return used[endd] == -1? false : true;
}
int fix_flow(int node , int endd , int fl)
{
if(node == endd || fl == 0)
return fl;
int idx , nb;
for(int i = to[node]; i < v[node].size(); i++ , to[node]++)
{
idx = v[node][i];
nb = e[idx].to;
if(used[nb] != used[node] + 1)
continue;
if(e[idx].c <= e[idx].flow)
continue;
int fix = fix_flow(nb , endd , min(fl , e[idx].c - e[idx].flow));
if(fix == 0)
continue;
e[idx].flow += fix;
e[idx ^ 1].flow -= fix;
return fix;
}
return 0;
}
int find_flow(int start , int endd)
{
int ans = 0;
while(bfs(start , endd) == true)
{
for(int i = 0; i <= n; i++)
to[i] = 0;
int curr;
while((curr = fix_flow(start , endd , INF)))
ans += curr;
}
return ans;
}
};
int type[maxn];
void bfs(int start)
{
type[start] = 1;
queue <int> q;
q.push(start);
while(q.size() != 0)
{
int node = q.front();
q.pop();
for(int& e : v[node])
{
if(type[e] != 0)
continue;
if(type[node] == 1)
type[e] = 2;
else
type[e] = 1;
q.push(e);
}
}
}
int findSample(int n, int confidence[], int host[], int protocol[])
{
max_flow G;
for(int i = 0; i < n; i++)
c[i] = confidence[i];
for(int i = 1; i < n; i++)
if(protocol[i] == 0)
add(host[i], i);
else if(protocol[i] == 1)
for(int& e : v[host[i]])
add(e, i);
else
{
for(int& e : v[host[i]])
add(e, i);
add(host[i], i);
}
for(int node = 0; node < n; node++)
if(type[node] == 0)
bfs(node);
G.init(n + 3);
for(int i = 0; i < n; i++)
if(type[i] == 2)
G.add_edge(i , n + 1 , 1);
else
{
for(int& e : v[i])
G.add_edge(i , e , 1);
G.add_edge(n , i , 1);
}
return n - G.find_flow(n , n + 1);
}
/**int main()
{
#ifdef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
///startT = std::chrono::high_resolution_clock::now();
add(1 , 1 , 10 , 2 , 9 , 4);
_remove(1 , 1 , 10 , 5 , 10 , 1);
_remove(1 , 1 , 10 , 4 , 7 , 5);
add(1 , 1 , 10 , 1 , 6 , 3);
add(1 , 1 , 10 , 3 , 3 , 5);
_remove(1 , 1 , 10 , 7 , 8 , 0);
answer(1 , 1 , 10);
for(int i = 0; i < 10; i++)
cout << ans[i] << " ";
cout << endl;
return 0;
}
*/
