#include "beechtree.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "debugger.cpp"
#else
#define debug(...)
#endif
using namespace std;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long
template<typename T>
int len(T &a){
return a.size();
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int> beechtree(int n, int m, std::vector<int> par, std::vector<int> col)
{
assert(n <= 8);
vector<vector<int>> g(n);
for(int i = 1; i < n; i ++){
g[par[i]].push_back(i);
col[i] --;
}
vector<int> res(n);
vector<int> cnt(m + 1);
auto check = [&](int &node, vector<int> &perm){
if(perm[0] != node) return false;
vector<int> f(len(perm));
for(int i = 1; i < len(perm); i ++){
f[i] = cnt[col[perm[i]]];
cnt[col[perm[i]]] ++;
}
for(int i = 1; i < len(perm); i ++) cnt[col[perm[i]]] --;
//debug(f, cnt);
for(int i = 1; i < len(perm); i ++){
if(perm[f[i]] != par[perm[i]]) return false;
}
return true;
};
auto dfs = [&](auto &dfs, int i)->vector<int>{
vector<int> perm = {i};
for(auto u : g[i]){
auto r = dfs(dfs, u);
if(len(perm) < len(r)) swap(perm, r);
for(auto u : r) perm.push_back(u);
}
sort(all(perm));
//debug(perm);
do{
if(check(i, perm)){
res[i] = 1;
break;
}
}while(next_permutation(all(perm)));
return perm;
};
dfs(dfs, 0);
return res;
}
