// D. Beech Tree
#include<bits/stdc++.h>
#include "beechtree.h"
using namespace std;
using g_t = vector<vector<int>>;
struct dVal {
map<int,int> de;
list<set<pair<int,int>>> se;
int seSi;
};
vector<int> de;
vector<int> de2;
dVal dfs(int n, g_t &g, vector<bool> &po, vector<int> &c) {
map<int, int> r;
map<int, vector<pair<int, int>>> ve;
list<set<pair<int, int>>> se;
map<int, map<int,int>> OmiR;
int seSi = 0;
for (auto e: g[n]) {
if (r.find(c[e]) != r.end()) po[n] = false;
r[c[e]] = 1;
ve[c[e]] = {};
}
for (auto e: g[n]) {
auto [re, li, ssi] = dfs(e, g, po, c);
if (!po[e]) {
po[n] = false;
}
if (!po[n]) continue;
for (auto &[co, d]: re) {
if (r.find(co) == r.end()) {
po[n] = false;
break;
}
if (co == c[e]) r[c[e]] = d + 1;
ve[co].emplace_back(d, e);
}
if (!po[n]) continue;
if (ssi > seSi) {
swap(se, li);
swap(ssi, seSi);
}
auto itS = se.begin();
for (auto &it: li) {
while (itS != se.end() && itS->size() <= it.size()) {
for (auto cos: *itS) {
if (it.erase(cos) == 0) {
po[n] = false;
break;
}
}
if (!po[n]) break;
itS++;
}
if (!po[n]) break;
if (!it.empty()) {
auto act = se.insert(itS, set<pair<int, int>>());
for (auto cos: it) {
if (itS->erase(cos) == 0) {
po[n] = false;
break;
}
act->insert(cos);
}
}
if (itS->empty()) itS++;
if (!po[n]) break;
}
}
if (!po[n]) return {};
se.emplace_back();
for (auto &[co, vec]: ve) {
bool dD = true;
for (auto [d, e]: vec) {
if (d > r[co]) {
po[n] = false;
return {};
} else if (d == r[co]) {
dD = false;
break;
}
}
if (dD) {
se.back().insert({co, r[co]});
seSi++;
}
}
if (se.back().empty()) se.pop_back();
de[n] = seSi;
return {std::move(r), std::move(se), seSi};
}
pair<array<map<int,map<int,int>>,2>, int> sdfs(int n, g_t& g, vector<bool>& po, vector<int>& c, vector<bool>&vis) {
if (vis[n]) return {};
vis[n] = true;
array<map<int,map<int,int>>,2> res;
int reSi = 0;
for (auto e: g[n]) {
auto [re, si] = sdfs(e, g, po, c,vis);
if (!po[e]) po[n] = false;
if (!po[n]) continue;
re[0][c[e]][de2[e]] = re[1][c[e]][de2[e]] = de2[n];
si++;
if (si > reSi) {
swap(re, res);
swap(reSi, si);
}
for (auto &[co, ma]: re[1]) {
for (auto &[don, par]: ma) {
if (res[0][co].upper_bound(don) != res[0][co].end() && res[0][co].upper_bound(don)->second < par) {
po[n] = false;
break;
}
if (res[1][co].find(don) == res[1][co].end()) reSi++;
res[1][co][don] = min(res[1][co][don], par);
}
if (!po[n]) break;
}
if (!po[n]) break;
for (auto &[co, ma]: re[0]) {
for (auto &[don, par]: ma) {
res[0][co][don] = max(res[0][co][don], par);
}
if (!po[n]) break;
}
}
return {std::move(res), reSi};
}
void bfs(int n, g_t& g, vector<bool>& vi) {
int d= 0;
int pre = -1;
int preD = de[n];
priority_queue<tuple<int,int,int>> pq;
pq.push({de[n], 1, n});
while (!pq.empty()) {
auto [dep, pr, t] = pq.top();
pq.pop();
if (vi[t]) continue;
vi[t] = true;
pr = -pr;
if (pre != pr || preD != de[t]) d++;
de2[t] = d;
pre = pr;
preD = de[t];
for (auto e: g[t]) {
pq.push({de[e], -d, e});
}
}
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
g_t g(N);
for (int i = 1; i < N; ++i) {
g[P[i]].push_back(i);
}
de = vector<int>(N);
de2 = vector<int>(N, -1);
vector<bool> po(N, true);
dfs(0, g, po, C);
vector<bool> vis(N, false);
for (int i = 0; i < N; ++i) {
if (po[i]) {
bfs(i, g, vis);
}
}
std::fill(vis.begin(), vis.end(),false);
for (int i = 0; i < N; ++i) {
if (po[i]) {
sdfs(i, g, po, C, vis);
}
}
return {po.begin(), po.end()};
}
#ifndef EVAL
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
vector<int> p(n), c(n);
for (auto &e: p) {
cin >> e;
}
for (auto &e: c) {
cin >> e;
}
auto res = beechtree(n, m, p, c);
for (auto e: res) {
cout << e << " ";
}
cout << "\n";
}
#endif
