Färbung von Geysiren#11731
Einst fand Lucy eine Höhle auf einem der Planeten im Link-Cut-System. Die Höhle besteht aus Hallen und n - 1 Durchgängen; jeder Durchgang verbindet zwei Hallen, und es ist möglich, von jeder Halle aus über die Durchgänge zu jeder anderen Halle zu gelangen.
In jeder Halle gibt es einen Färbegeysir. Wenn der Färbegeysir in Halle Nummer ausbricht, färbt er alle Hallen, die sich in einer Entfernung von höchstens d_i von Halle befinden, in der Farbe Nummer . Die Entfernung zwischen zwei Hallen wird als die minimale Anzahl von Durchgängen definiert, die man durchqueren muss, um zwischen ihnen zu gelangen.
Lucy kennt die Struktur der Höhle, die Farben einiger Hallen und dass jeder Geysir genau einmal ausgebrochen ist. Basierend auf diesen Informationen soll eine mögliche Reihenfolge bestimmt werden, in der die Ausbrüche stattgefunden haben könnten.
Die erste Zeile enthält eine einzelne ganze Zahl (2 \le n \le 10^5) — die Anzahl der Hallen in der Höhle.
Die zweite Zeile enthält ganze Zahlen d_1, d_2, ... , d_n (0 \le d_i \le n - 1) — die Entfernungsfärbeparameter für die Geysire.
Die dritte Zeile enthält ganze Zahlen c_1, c_2, ... , c_n (-1 \le c_i \le n), wobei c_i entweder die Farbnummer der -ten Halle oder ist, wenn die Farbe der -ten Halle unbekannt ist.
Die nächsten n - 1 Zeilen beschreiben die Durchgänge. Die -te Zeile enthält zwei ganze Zahlen u_i, v_i (1 \le u_i, v_i \le n, u_i \ne v_i) — die Hallen, die durch den Durchgang verbunden sind.
Geben Sie in einer einzigen Zeile ganze Zahlen p_1, p_2, ... , p_n aus, wobei p_i die Nummer der Halle ist, in der sich der Geysir befindet, der als -ter ausgebrochen ist. Es ist garantiert, dass es mindestens eine Reihenfolge gibt, die den Eingabedaten entspricht.
Beispiel
Beispiel 1
Im ersten Beispiel sind hier die Farben der Hallen nach jedem Ausbruch, vorausgesetzt, sie fanden in der angegebenen Reihenfolge in der Ausgabe statt:
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
( Punkte): n \le 8;
( Punkte): d_i = 1 (1 \le i \le n);
( Punkte): u_i = 1 (1 \le i \le n - 1);
( Punkte): n \le 5 \cdot 10^4;
( Punkte): keine zusätzlichen Einschränkungen.