#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> piii;
int N, M;
vector<int> adj[202020];
vector<int> P, C;
int cnt[202020];
int idx[202020];
vector<int> V;
int D[202020];
int deg[202020];
void dfs(int v) {
V.push_back(v);
for (int i : adj[v]) dfs(i);
}
bool solve(int rt) {
for (int i = 1; i <= M; i++) cnt[i] = 0;
V.clear();
dfs(rt);
for (int i : V) {
D[i] = 0;
deg[i] = adj[i].size();
}
{
priority_queue<piii, vector<piii>, greater<piii>> pq;
for (int i : V) {
if (!deg[i]) pq.emplace(0, 0, i);
}
int bef = -1;
while (pq.size()) {
int x = get<2>(pq.top()); pq.pop();
if (bef != -1 && adj[bef].size() < adj[x].size()) D[x] = max(D[x], D[bef] + 1);
if (x != rt) {
deg[P[x]]--;
D[P[x]] = max(D[P[x]], D[x] + 1);
if (!deg[P[x]]) pq.emplace(adj[P[x]].size(), D[P[x]], P[x]);
}
bef = x;
}
}
priority_queue<tuple<int, int, int, int>> pq;
pq.emplace(D[rt], 0, 0, rt);
int id = 0;
while (pq.size()) {
int x = get<3>(pq.top()); pq.pop();
idx[x] = id++;
if (x != rt && cnt[C[x]]++ != idx[P[x]]) return false;
for (int i : adj[x]) pq.emplace(adj[i].size(), D[i], -idx[x], i);
}
return true;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
::N = N; ::M = M; ::P = P; ::C = C;
vector<int> ans(N);
for (int i = 1; i < N; i++) adj[P[i]].push_back(i);
for (int i = 0; i < N; i++) ans[i] = solve(i);
return ans;
}
