#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;
#define pll pair<int,int>
#define f first
#define s second
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<pll> clayer;
clayer.push_back({0, i});
int last=-1;
bool die=0;
while(!clayer.empty()){
vector<pll> nxtlayer;
sort(clayer.begin(),clayer.end(), [&](pll a, pll b){
if(a.f != b.f) return a.f > b.f;
return chcol[a.s].size() > chcol[b.s].size();
});
//printf("cur layer: ");
for(auto [psz, it] : clayer){
//cout<<it<<" ";
if(ok[it] == 0) die=1;
}
//cout<<'\n';
if(last != -1 and !check(last, clayer[0].s))die=1;
if(!die) for(int i=1;i<(int)clayer.size();i++){
if(!check(clayer[i-1].s, clayer[i].s)){
die=1;
break;
}
}
if(die)break;
for(auto [psz, it] : clayer){
for(auto to : al[it]){
nxtlayer.push_back({(int)chcol[it].size(), to});
}
}
last=clayer.back().s;
swap(nxtlayer, clayer);
}
if(die) ok[i]=0;
}
return ok;
}
