#include "beechtree.h"
#define pb push_back
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
int n, m, p[maxn], c[maxn];
vector < int > sub[maxn], g[maxn];
void dfs(int beg)
{
sub[beg].pb(beg);
for (auto nb: g[beg])
{
dfs(nb);
for (auto x: sub[nb])
sub[beg].pb(x);
}
}
int curr_root, sz, used[maxn], a[maxn];
map < int, int > mp;
int is;
void check()
{
mp.clear();
int no = 0;
for (int i = 0; i < sz; ++ i)
{
if(i != 0)
{
int fi = mp[c[a[i]]];
int exp_par = p[a[i]];
int par = a[fi];
if(exp_par != par)no = 1;
}
if(i != 0)mp[c[a[i]]] ++;
}
if(!no)is = 1;
}
void gen(int pos)
{
if(pos == sz)
{
check();
return;
}
for (int i = 0; i < (int)sub[curr_root].size(); ++ i)
{
if(used[i])
{
continue;
}
used[i] = 1;
a[pos] = sub[curr_root][i];
gen(pos + 1);
used[i] = 0;
}
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
n = N;
m = M;
for (int i = 0; i < n; ++ i)
{
p[i] = P[i];
c[i] = C[i];
if(p[i] != -1)g[p[i]].pb(i);
}
//dfs(0);
int mark = c[n-1], extend = n-1;
for (int i = n-1; i >= 0; -- i)
{
if(c[i] == mark)extend = i;
else break;
}
extend --;
vector < int > res;
for (int i = 0; i < n; ++ i)
{
if(i >= extend)res.pb(1);
else res.pb(0);
}
return res;
vector < int > ans;
for (int root = 0; root < n; ++ root)
{
curr_root = root;
sz = sub[root].size();
used[0] = 1;
a[0] = root;
is = 0;
gen(1);
used[0] = 0;
ans.pb(is);
}
return ans;
}
