#include "bits/stdc++.h"
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
bool is_path(vector<int> P){
for (int i = 1; i<P.size(); i++){
if (P[i]!=i-1) return false;
}
return true;
}
bool mx_cnt(vector<int> C, int M){
vector<int> cnt(M+1);
for (int e: C) cnt[e]++;
return *max_element(all(cnt))<=2;
}
bool task3(vector<int> P){
int N = P.size();
vector<vector<int>> g(N);
for (int i = 1; i<N; i++){
g[P[i]].push_back(i);
g[i].push_back(P[i]);
}
int res = 0;
auto dfs = [&] (auto&& self, int u, int p, int d) -> void {
res = max(res, d);
for (int e: g[u]){
if (e!=p){
self(self, e, u, d+1);
}
}
};
dfs(dfs, 0, 0, 0);
return res<=2;
}
vector<int> brute(int N, int M, vector<int> P, vector<int> C){
vector<int> R(N);
vector<vector<int>> g(N);
for (int i = 1; i<N; i++){
g[P[i]].push_back(i);
g[i].push_back(P[i]);
}
vector<vector<int>> sub(N);
auto dfs = [&] (auto&& self, int u, int p) -> void {
for (int e: g[u]){
if (e!=p){
self(self, e, u);
for (int x: sub[e]) sub[u].push_back(x);
}
}
sort(all(sub[u]));
do {
map<int, int> cnt;
bool f = true;
vector<int> vec = sub[u];
vec.insert(vec.begin(), u);
for (int i = 1; i<vec.size(); i++){
int e = vec[i];
if (P[e]!=vec[cnt[C[e]]]){
f = false;
break;
}
cnt[C[e]]++;
}
if (f){
R[u] = 1;
break;
}
}
while(next_permutation(all(sub[u])));
sub[u].push_back(u);
};
dfs(dfs, 0, 0);
return R;
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C){
vector<int> R(N);
if (N<=8){
return brute(N, M, P, C);
}
else if (is_path(P)){
set<int> st;
for (int i = N-1; i>=0; i--){
if (st.size()<=1) R[i] = 1;
else break;
st.insert(C[i]);
}
return R;
}
else if (mx_cnt(C, M)){
vector<vector<int>> g(N);
for (int i = 1; i<N; i++){
g[P[i]].push_back(i);
g[i].push_back(P[i]);
}
vector<int> height(N);
auto dfs = [&] (auto&& self, int u, int p) -> void {
vector<int> ch;
int cnt = 0;
set<int> st;
for (int e: g[u]){
if (e!=p){
self(self, e, u);
height[u] = max(height[u], height[e]+1);
if (height[e]==1) ch.push_back(e);
st.insert(C[e]);
cnt++;
}
}
if (height[u]==0) R[u] = 1;
else if (height[u]==1){
if (st.size()==cnt) R[u] = 1;
}
else if (height[u]==2){
if (st.size()==cnt && ch.size()==1){
int v = ch[0];
bool f = true;
for (int e: g[v]){
if (e!=u){
if (st.find(C[e])==st.end()) f = false;
}
}
if (f) R[u] = 1;
}
}
};
dfs(dfs, 0, 0);
return R;
}
else if (task3(P)){
vector<vector<int>> g(N);
for (int i = 1; i<N; i++){
g[P[i]].push_back(i);
g[i].push_back(P[i]);
}
bool f = true;
set<int> ss;
set<int> ss2;
vector<set<int>> vv;
for (int i = 0; i<N; i++){
set<int> st;
int cnt = 0;
for (int e: g[i]){
if (e!=P[i]) {
cnt++;
st.insert(C[e]);
}
}
if (st.size()==cnt) R[i] = 1;
else f = false;
if (i==0){
ss = st;
}
else {
for (int e: st){
if (ss.find(e)==ss.end()) f = false;
}
for (int e: st) ss2.insert(e);
vv.push_back(st);
}
}
bool gg = false;
for (set<int> s: vv){
if (s.size()==ss2.size()) gg = true;
}
R[0] = (f && gg);
return R;
}
return {};
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int main(){
// int t = 1000;
// int n = 5;
// int u = 0;
// while(t--){
// vector<int> P(n), C(n);
// P[0] = -1;
// for (int i = 1; i<n; i++) P[i] = rng()%i;
// for (int i = 0; i<n; i++) C[i] = rng()%(n+1)+1;
// vector<int> R1 = beechtree(n, 10, P, C);
// vector<int> R2 = brute(n, 10, P, C);
// if (R1!=R2 && R1.size()){
// for (int e: P) cout<<e<<" ";
// cout<<endl;
// for (int e: C) cout<<e<<" ";
// cout<<endl;
// cout<<endl;
// for (int e: R1) cout<<e<<" ";
// return 0;
// }
// else {
// u++;
// }
// }
// cout<<u<<endl;
// // vector<int> R1 = beechtree(5, 10, {-1, 0, 0, 2, 1}, {5, 3, 4, 4, 4});
// // vector<int> R2 = brute(5, 10, {-1, 0, 0, 2, 1}, {5, 3, 4, 4, 4});
// // for (int e: R1) cout<<e<<" ";
// // cout<<endl;
// // for (int e: R2) cout<<e<<" ";
// }
