#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;
#define pb push_back
const int N=2005,M=2e5+5;
int a[N],fa[N],L[N],R[N],ord[N],dep[N],ans[N],vs[M],z[N][N],z1[N][N];
struct Edge {int v,x;};vector<Edge> e[N];
void dfs(int u)
{ord[L[u]=++L[0]]=u;for(auto [v,x]:e[u]) dep[v]=dep[u]+1,dfs(v);R[u]=L[0];}
void dfs1(int u)
{
    ans[u]=1;for(auto [v,x]:e[u]) dfs1(v);
    for(auto [v,x]:e[u]) if(!ans[v]) {ans[u]=0;return;}
    for(auto [v,x]:e[u]) for(int i1=L[v],i=ord[i1];i1<=R[v];i=ord[++i1])
        for(int j1=L[u],j=ord[j1];j1<L[v];j=ord[++j1])
            if(z[i][j]==3 || z1[i][j]==3) {ans[u]=0;return;}
}
vector<int> beechtree(int n,int m,vector<int> _fa,vector<int> _a)
{
    vector<int> res(n);for(int i=1;i<=n;++i) fa[i]=_fa[i-1]+1,a[i]=_a[i-1];
    for(int i=2;i<=n;++i) e[fa[i]].pb((Edge) {i,a[i]});dep[1]=1;dfs(1);
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
    {
        ++vs[0];for(auto [v,x]:e[i]) {if(vs[x]==vs[0]) z1[i][j]=3;vs[x]=vs[0];}
        for(auto [v,x]:e[j]) if(vs[x]!=vs[0]) z1[i][j]|=1;
        ++vs[0];for(auto [v,x]:e[j]) {if(vs[x]==vs[0]) z1[i][j]=3;vs[x]=vs[0];}
        for(auto [v,x]:e[i]) if(vs[x]!=vs[0]) z1[i][j]|=2;
    }
    for(int i=n;i;--i) for(int j=n;j;--j)
    {
        if(e[i].size()<e[j].size()) z[i][j]=1;
        if(e[i].size()>e[j].size()) z[i][j]=2;
        for(auto [i1,x]:e[i]) for(auto [j1,y]:e[j])
            if(x==y) z[i][j]|=z[i1][j1];
    }dfs1(1);copy(ans+1,ans+n+1,res.begin());return res;
}