#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define el '\n'
#define ff first
#define ss second
#define pii pair <ll, ll>
#define pb push_back
#define mkp make_pair
#define fr(i, l, r) for(ll i = l; i <= r; i++)
#define debug(x) \
{ cout << #x << " = " << x << el; }
template<class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template<class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
const ll N = 2e5 + 10;
const ll M = 1e5 + 10;
const ll K = 400;
const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll LOG = 20;
const ll mod = 1000002022;
mt19937 rnd(time(0));
int p[N], c[N], cnt[N], sz[N], h[N];
vector <int> g[N], x, ans;
void dfs1(int v) {
x.pb(v);
for(int u : g[v])
dfs1(u);
}
bool comp(int a, int b) {
return sz[a] > sz[b];
}
int check(vector <int> &v) {
int k = 1;
for(int j = 1; j < v.size(); j++) {
int par = cnt[c[v[j]]];
cnt[c[v[j]]]++;
if(p[v[j]] != v[par]) k = 0;
}
for(int j = 0; j < v.size(); j++)
cnt[c[v[j]]] = 0;
return k;
}
/*
10 3
-1 0 0 0 1 1 1 2 2 3
0 2 3 1 3 1 2 3 2 1
*/
void dfs2(int v) {
h[v] = 0;
sz[v] = 1;
int mx = 0, good = 1;
for(int u : g[v]) {
cnt[c[u]]++;
chmax(mx, cnt[c[u]]);
}
for(int u : g[v])
cnt[c[u]] = 0;
for(int u : g[v]) {
dfs2(u);
chmax(h[v], h[u] + 1);
sz[v] += sz[u];
good &= ans[u];
}
if(mx > 1 || h[v] > 2 || !good) return;
if(h[v] <= 1) {
ans[v] = 1;
return;
}
sort(g[v].begin(), g[v].end(), comp);
vector <int> p = {v};
for(int i : g[v])
p.pb(i);
for(int i : g[v])
for(int i2 : g[i])
p.pb(i2);
if(check(p)) ans[v] = 1;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) {
fr(i, 0, N - 1) {
p[i] = P[i];
c[i] = C[i];
if(i) g[p[i]].pb(i);
}
ans.resize(N);
bool k = 1;
fr(i, 0, N - 1)
k &= (p[i] == i - 1);
if(k) {
int cnt = 0;
for(int i = N - 1; i >= 0; i--) {
if(i + cnt == N - 1) ans[i] = 1;
cnt += (C[i] == C[N - 1]);
}
return ans;
}
if(N <= 8) {
vector <int> ans(N);
fr(i, 0, N - 1) {
x.clear();
dfs1(i);
sort(x.begin(), x.end());
int good = 0;
do {
int k = 1;
if(x[0] != i)
continue;
for(int j = 1; j < x.size(); j++) {
int par = cnt[c[x[j]]];
cnt[c[x[j]]]++;
if(p[x[j]] != x[par]) k = 0;
}
for(int j = 0; j < x.size(); j++)
cnt[c[x[j]]] = 0;
if(k) {
good = 1;
break;
}
}while(next_permutation(x.begin(), x.end()));
ans[i] = good;
}
return ans;
}
dfs2(0);
return ans;
}
/*
int main()
{
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> P(N);
for (int i = 0; i < N; ++i)
assert(1 == scanf("%d", &P[i]));
std::vector<int> C(N);
for (int i = 0; i < N; ++i)
assert(1 == scanf("%d", &C[i]));
fclose(stdin);
std::vector<int> res = beechtree(N, M, P, C);
int n = res.size();
for (int i = 0; i < n; ++i)
{
if (i > 0)
printf(" ");
printf("%d", res[i]);
}
printf("\n");
fclose(stdout);
return 0;
}
*/
