#include "friend.h"
#include<bits/stdc++.h>
#define pb emplace_back
#define vi vector<int>
using namespace std;
// Find out best sample
/*
6
13 3 6 20 10 15
0 0
0 1
1 2
2 1
0 0
*/
bool f[1005][1005];
vi E[1005];
int dp[1005][5], side[1005];
void addedge(int x,int h, int ope){
if(ope == 0) side[x] = side[h]^1, f[x][h] = f[h][x] = 1, E[h].pb(x), E[x].pb(h);
else if(ope == 1){
side[x] = side[h];
for(int i=0;i<x;i++){
if(f[h][i]) f[x][i] = f[i][x] = 1, E[x].pb(i), E[i].pb(x);
}
}
else{
for(int i=0;i<x;i++){
if(i == h || f[h][i]) f[i][x] = f[x][i] = 1, E[i].pb(x), E[x].pb(i);
}
}
}
bool ok(vi &v){
/* for(auto i:v) cout<<i<<" "; cout<<'\n'; */
int n = v.size();
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(f[v[i]][v[j]]) return 0;
return 1;
}
int val[1005];
void dfs(int x,int p){
for(auto &i:E[x]){
if(i==p) continue;
dfs(i, x);
}
dp[x][0] = 0;
dp[x][1] = val[x];
for(auto &i:E[x]){
if(i==p) continue;
dp[x][1] += dp[i][0];
dp[x][0] += max(dp[i][0], dp[i][1]);
}
}
bool vis[1005];
int match[1005];
bool dfs_match(int x){
vis[x] = 1;
for(auto &i:E[x]){
if(match[i] == -1){
match[i] = x;
match[x] = i;
return 1;
}
else if(!vis[match[i]] && dfs_match(match[i])){
match[i] = x;
match[x] = i;
return 1;
}
}
return 0;
}
int findSample(int n,int conf[],int host[],int ope[]){
for(int i=1;i<n;i++) addedge(i, host[i], ope[i]);
for(int i=0;i<n;i++) val[i] = conf[i];
if(n <= 10){
int all = 1<<n, ans = 0;
for(int i=1;i<all;i++){
vector<int> v;
for(int j=0;j<n;j++){
if(i>>j&1) v.pb(j);
}
if(ok(v)){
int ta = 0;
for(auto &x:v) ta += conf[x];
ans = max(ans, ta);
}
}
return ans;
}
else if(*max_element(conf, conf+n) == 1){
memset(match, -1, sizeof(match));
int ans = 0;
/* for(int i=0;i<n;i++) cout<<side[i]<<" \n"[i==n-1]; */
for(int i=0;i<n;i++){
if(!side[i]){
memset(vis, 0, sizeof(vis));
ans += dfs_match(i);
}
}
return n - ans;
}
else if(ope[1] == 2){
return *max_element(conf, conf+n);
}
else if(ope[1] == 0){
int ans = 0;
for(int i=0;i<n;i++){
if(!dp[i][1]){
dfs(i, -1);
ans += max(dp[i][0], dp[i][1]);
}
}
return ans;
}
}
