#include <bits/stdc++.h>
#include "friend.h"
#define ad push_back
using namespace std;
const int N = 1010;
int n;
vector <int> g[N];
bool col[20][20];
int dp[N][2];
int sz[N];
bool cl[N];
int findmn()
{
int mn = n, ret = -1;
for (int i = 0; i < n; i++)
{
if(cl[i]) continue;
if(sz[i] < mn) mn = sz[i], ret = i;
}
return ret;
}
void dfs(int v, int par)
{
int sum = 0, sm = 0;
for(auto p : g[v])
{
if(p == par) continue;
dfs(p, v);
sum += dp[p][0];
sm += max(dp[p][1], dp[p][0]);
}
dp[v][0] = sm;
dp[v][1] += sum;
}
int findSample(int n1,int c[],int host[],int pr[])
{
n = n1;
bool mk, erk, erq;
mk=erk=erq=0;
for (int i = 1; i < n; i++)
{
if(pr[i] == 0)
{
g[host[i]].ad(i);
g[i].ad(host[i]);
mk = 1;
}
else if(pr[i] == 1)
{
for(auto p : g[host[i]]) g[p].ad(i), g[i].ad(p);
erk = 1;
}
else
{
for(auto p : g[host[i]]) g[p].ad(i), g[i].ad(p);
g[host[i]].ad(i);
g[i].ad(host[i]);
erq = 1;
}
}
if(n <= 10)
{
for (int i = 0; i < n; i++)
for(auto p : g[i]) col[i][p] = 1;//, cout << i << " " << p << endl;
int pat = 0;
for(int x = 0; x < (1 << n); ++x)
{
int sum = 0;
vector <int> sm;
for (int i = 0; i < n; i++)
if(x & (1 << i)) sum += c[i], sm.ad(i);
bool bl = 0;
for(auto p : sm)
for(auto p1 : sm) if(col[p][p1]) bl = true;
if(!bl) pat = max(pat, sum);
}
return pat;
}
if(!mk && erk && !erq)
{
int pat = 0;
for (int i = 0; i < n; i++)
pat += c[i];
return pat;
}
if(!mk && !erk && erq)
{
int pat = 0;
for (int i = 0; i < n; i++)
pat = max(pat, c[i]);
return pat;
}
if(mk && !erk && !erq)
{
for (int i = 0; i < n; i++) dp[i][1] = c[i];
dfs(0, 0);
return max(dp[0][0], dp[0][1]);
}
else
{
int pat = 0;
while(1)
{
int sm = findmn();
if(sm == -1) break;
pat++;
cl[sm] = 1;
for(auto p : g[sm]) cl[p] = 1, sz[p]--;
}
return pat;
}
}
