#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{
vector<int> ok(N, 1);
vector<set<int>> chcol(N);
vector<vector<int>> al(N);
for(int i=1;i<N;i++){
if(chcol[P[i]].find(C[i]) != chcol[P[i]].end()){
ok[P[i]]=0;
}
al[P[i]].push_back(i);
chcol[P[i]].insert(C[i]);
}
auto check=[&](int a, int b)->bool{
for(auto it : chcol[b]){
if(chcol[a].find(it) == chcol[a].end()) return 0;
}
return 1;
};
for(int i=0;i<N;i++){
vector<int> clayer;
clayer.push_back(i);
int last=-1;
bool die=0;
while(!clayer.empty()){
vector<int> nxtlayer;
sort(clayer.begin(),clayer.end(), [&](int a, int b){
return chcol[a].size() > chcol[b].size();
});
//printf("cur layer: ");
for(auto it : clayer){
//cout<<it<<" ";
if(ok[it] == 0) die=1;
}
//cout<<'\n';
if(last != -1 and !check(last, clayer[0]))die=1;
if(!die) for(int i=1;i<(int)clayer.size();i++){
if(!check(clayer[i-1], clayer[i])){
die=1;
break;
}
}
if(die)break;
for(auto it : clayer){
for(auto to : al[it]){
nxtlayer.push_back(to);
}
}
last=clayer.back();
swap(nxtlayer, clayer);
}
if(die) ok[i]=0;
}
return ok;
}
