Coloring Geysers#11731
Once, Lucy found a cave on one of the planets in the Link-Cut system. The cave consists of halls and n - 1 passages; each passage connects two halls, and it is possible to reach any other hall from any hall through the passages.
In each hall, there is a coloring geyser. When the coloring geyser in hall number erupts, it colors all halls that are at a distance of no more than d_i from hall in color number . The distance between two halls is defined as the minimum number of passages you need to travel through in order to move between them.
Lucy knows the structure of the cave, the colors of some halls, and that each geyser erupted exactly once. Based on this information, determine any possible order in which the eruptions could have occurred.
The first line contains a single integer (2 \le n \le 10^5) — the number of halls in the cave.
The second line contains integers d_1, d_2, ... , d_n (0 \le d_i \le n - 1) — the distance coloring parameters for the geysers.
The third line contains integers c_1, c_2, ... , c_n (-1 \le c_i \le n), where c_i is either the color number of the -th hall or , if the color of the -th hall is unknown.
The next n - 1 lines describe the passages. The -th line contains two integers u_i, v_i (1 \le u_i, v_i \le n, u_i \ne v_i) — the halls connected by the passage.
In a single line, output integers p_1, p_2, ... , p_n, where p_i is the number of the hall where the geyser which erupted -th is located. It is guaranteed that there is at least one order that corresponds to the input data.
Example
Example 1
In the first example, here are the colors of halls after each eruption, assuming they happened in the order given in output:
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): no additional constraints.