#include "beechtree.h"
#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
vector<int> beechtree(int n, int m, vector<int> P, vector<int> C) {
vector<vector<pair<int,int>>> adj(n+1);
set<int> colors;
for(int i=0;i<n-1;i++){
int u = P[i]+1, v = i+2, col = C[i];
adj[u].push_back({v, col});
adj[v].push_back({u, col});
colors.insert(col);
}
int root = 1;
vector<int> parent(n+1), pcol(n+1);
vector<vector<pair<int,int>>> children(n+1);
function<void(int,int,int)> dfs1 = [&](int x, int p, int col){
parent[x] = p;
pcol[x] = col;
for(auto &pr : adj[x]){
int y = pr.first, col_e = pr.second;
if(y==p) continue;
children[x].push_back({y, col_e});
dfs1(y, x, col_e);
}
};
dfs1(root, 0, 0);
vector<ll> subsize(n+1);
vector<unordered_map<int,ll>> childSize(n+1);
bool ok = true;
function<void(int)> dfs2 = [&](int x){
subsize[x] = 1;
unordered_map<int,int> seen;
for(auto &pr : children[x]){
int y = pr.first, col = pr.second;
dfs2(y);
if(++seen[col] > 1) ok = false;
childSize[x][col] = subsize[y];
subsize[x] += subsize[y];
}
};
dfs2(root);
if(!ok) return {};
for(int col : colors){
ll smin = LLONG_MAX;
for(int i=1;i<=n;i++){
auto it = childSize[i].find(col);
if(it!=childSize[i].end()) smin = min(smin, subsize[i]);
}
if(smin==LLONG_MAX) continue;
for(int i=1;i<=n;i++){
if(subsize[i] >= smin && childSize[i].count(col)==0){ ok = false; break; }
}
if(!ok) break;
vector<pair<ll,ll>> vec;
for(int i=1;i<=n;i++){
auto it = childSize[i].find(col);
ll z = (it==childSize[i].end()?0:it->second);
vec.push_back({subsize[i], z});
}
sort(vec.begin(), vec.end());
ll last = -1;
for(auto &pr : vec){ if(pr.second < last){ ok=false; break;} last=pr.second; }
if(!ok) break;
}
if(!ok) return {};
priority_queue<pair<ll,int>> pq;
pq.push({subsize[root], root});
vector<int> order;
order.reserve(n);
while(!pq.empty()){
auto [sz, x] = pq.top(); pq.pop();
order.push_back(x);
for(auto &pr : children[x]){
pq.push({subsize[pr.first], pr.first});
}
}
reverse(order.begin(), order.end());
vector<int> res(n);
for(int i=0;i<n;i++) res[order[i]-1] = i;
return res;
}
