// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
map<int,int>e[maxn];
vi g[maxn];
vi res;

int sz[maxn],son[maxn];
void dfs0(int u){
	sz[u]=1,son[u]=-1;
	for(auto v:g[u]){
		dfs0(v),sz[u]+=sz[v];
		if(son[u]==-1 || sz[v]>sz[son[u]]) son[u]=v;
	}
}

bool chk(int u,int v){
	for(auto [c,x]:e[v])
		if(!e[u].count(c) || sz[e[u][c]]<sz[x]) return 0;
	return 1;
}
set<pii>s[maxn];
void dfs1(int u){
	for(auto v:g[u]){
		dfs1(v);
		if(!res[v])res[u]=0;
	}
	if(!res[u])return;
	if(son[u]==-1){
		s[u].insert(mkp(sz[u],u));
		return;
	}
	swap(s[u],s[son[u]]);
	if(!chk(u,(s[u].begin())->se)) {
		res[u]=0; return;
	}
	s[u].insert(mkp(sz[u],u));
	for(int v:g[u])
		if(v!=son[u]){
			for(auto it:s[v]){
				auto R=s[u].lower_bound(it);
				if(R!=s[u].end() && !chk(R->se,it.se)){
					res[u]=0;
					return;
				}
				if(R!=s[u].begin() && !chk(it.se,prev(R)->se)){
					res[u]=0;
					return;
				}
			}
			for(auto it:s[v]) s[u].insert(it);
		}
	return;
}

vi beechtree(int n,int m,vi P,vi C){
	res.resize(n,1);
	For(i,1,n-1) {
		g[P[i]].pb(i);
		if(e[P[i]].count(C[i])) res[P[i]]=0;
		else e[P[i]][C[i]]=i;
	}
	dfs0(0);
	dfs1(0);
	return res;
}