Coloration des Geysers#11731
Un jour, Lucy a trouvé une grotte sur l'une des planètes du système Link-Cut. La grotte se compose de salles et de n - 1 passages ; chaque passage relie deux salles, et il est possible d'atteindre n'importe quelle autre salle depuis n'importe quelle salle à travers les passages.
Dans chaque salle, il y a un geyser de coloration. Lorsque le geyser de coloration dans la salle numéro entre en éruption, il colore toutes les salles qui sont à une distance de pas plus de d_i de la salle en couleur numéro . La distance entre deux salles est définie comme le nombre minimum de passages que vous devez traverser pour vous déplacer entre elles.
Lucy connaît la structure de la grotte, les couleurs de certaines salles, et sait que chaque geyser a éclaté exactement une fois. Sur la base de ces informations, déterminez un ordre possible dans lequel les éruptions auraient pu se produire.
La première ligne contient un entier unique (2 \le n \le 10^5) — le nombre de salles dans la grotte.
La deuxième ligne contient entiers d_1, d_2, ... , d_n (0 \le d_i \le n - 1) — les paramètres de distance de coloration pour les geysers.
La troisième ligne contient entiers c_1, c_2, ... , c_n (-1 \le c_i \le n), où c_i est soit le numéro de couleur de la -ème salle soit , si la couleur de la -ème salle est inconnue.
Les n - 1 lignes suivantes décrivent les passages. La -ème ligne contient deux entiers u_i, v_i (1 \le u_i, v_i \le n, u_i \ne v_i) — les salles reliées par le passage.
Sur une seule ligne, affichez entiers p_1, p_2, ... , p_n, où p_i est le numéro de la salle où se trouve le geyser qui a éclaté en -ème. Il est garanti qu'il existe au moins un ordre qui correspond aux données d'entrée.
Exemple
Exemple 1
Dans le premier exemple, voici les couleurs des salles après chaque éruption, en supposant qu'elles se soient produites dans l'ordre donné dans la sortie :
1, 1, 1, 1, 1
5, 1, 1, 1, 5
4, 1, 1, 4, 5
3, 1, 3, 4, 5
2, 2, 3, 4, 5
( points) : n \le 8 ;
( points) : d_i = 1 (1 \le i \le n) ;
( points) : u_i = 1 (1 \le i \le n - 1) ;
( points) : n \le 5 \cdot 10^4 ;
( points) : pas de contraintes supplémentaires.