E. Paint it really, really dark gray

我看到一只粉红色的野猪，我想把它涂成黑色。黑色的野猪看起来比粉红色的更威武、更强大。自从Jaggy成为森林的统治者以来，他一直尽力改善森林地区与邻近地区之间的外交关系。 然而，一些其他统治者为和平提出了过多的条件，因此他意识到必须诉诸恐吓。一旦邻近地区的外交代表访问Jaggy的森林，如果他们看到一大群黑色的野猪，他们可能会突然改变攻击Jaggy的念头。毕竟，黑色的野猪真的很吓人。 Jaggy的森林可以用一棵树（无环的连通图）表示，包含 #cf_span[n] 个顶点。每个顶点代表一只野猪，颜色为黑色或粉红色。Jaggy派出一只松鼠在森林中游历，将所有野猪涂成黑色。然而，这只松鼠的训练方式非常特殊：当它遍历图时，会改变它访问的每个顶点的颜色，无论其初始颜色如何：粉红色顶点变为黑色，黑色顶点变为粉红色。 由于Jaggy太忙而无法规划松鼠的路线，他需要你的帮助。他希望你构造一条从顶点 #cf_span[1] 出发的路径，使得最终所有顶点都为黑色。路径是一系列顶点，其中每一对连续顶点之间在树中都有边相连。 输入的第一行包含整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 200 000]），表示树中顶点的数量。接下来的 #cf_span[n] 行包含 #cf_span[n] 个整数，表示各节点的颜色。 如果第 #cf_span[i] 个整数为 #cf_span[1]，表示第 #cf_span[i] 个顶点为黑色；如果为 #cf_span[ - 1]，表示第 #cf_span[i] 个顶点为粉红色。 接下来的 #cf_span[n - 1] 行每行包含两个整数，表示由边连接的两个顶点的编号。顶点编号从 #cf_span[1] 开始。 请输出松鼠的路径：按访问顺序输出访问的节点编号序列。如果所有节点初始均为黑色，则应输出 #cf_span[1]。保证解存在。如果存在多个解，你可以输出任意一个，只要序列长度不超过 #cf_span[107] 即可。 开始时松鼠位于节点 1，其颜色为黑色。后续步骤如下： ## Input 输入的第一行包含整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 200 000]），表示树中顶点的数量。接下来的 #cf_span[n] 行包含 #cf_span[n] 个整数，表示各节点的颜色。如果第 #cf_span[i] 个整数为 #cf_span[1]，表示第 #cf_span[i] 个顶点为黑色；如果为 #cf_span[ - 1]，表示第 #cf_span[i] 个顶点为粉红色。接下来的 #cf_span[n - 1] 行每行包含两个整数，表示由边连接的两个顶点的编号。顶点编号从 #cf_span[1] 开始。 ## Output 输出松鼠的路径：按访问顺序输出访问的节点编号序列。如果所有节点初始均为黑色，则应输出 #cf_span[1]。保证解存在。如果存在多个解，你可以输出任意一个，只要序列长度不超过 #cf_span[107] 即可。 [samples] ## Note 开始时松鼠位于节点 1，其颜色为黑色。后续步骤如下： 从节点 #cf_span[1] 走到节点 #cf_span[4]，将其颜色变为粉红色。 从节点 #cf_span[4] 走到节点 #cf_span[2]，将其颜色变为粉红色。 从节点 #cf_span[2] 走到节点 #cf_span[5]，将其颜色变为黑色。 从节点 #cf_span[5] 返回节点 #cf_span[2]，将其颜色变为黑色。 从节点 #cf_span[2] 走到节点 #cf_span[4]，将其颜色变为黑色。 访问节点 #cf_span[3]，将其颜色变为黑色。 访问节点 #cf_span[4]，将其颜色变为粉红色。 访问节点 #cf_span[1]，将其颜色变为粉红色。 访问节点 #cf_span[4]，将其颜色变为黑色。 访问节点 #cf_span[1]，将其颜色变为黑色。

**Definitions:** - Let $ T = (V, E) $ be a tree with $ n $ vertices, where $ V = \{1, 2, \dots, n\} $. - Each vertex $ i \in V $ has an initial color $ c_i \in \{-1, 1\} $, where $ c_i = 1 $ means black, $ c_i = -1 $ means pink. - The squirrel starts at vertex $ 1 $. - Each time the squirrel visits a vertex, its color is flipped: $ c_i \leftarrow -c_i $. - The goal is to find a walk $ w = (v_1, v_2, \dots, v_k) $, with $ v_1 = 1 $, such that after traversing the walk, all vertices are black (i.e., final color of each vertex $ i $ is $ 1 $). **Constraints:** - The walk must be a valid path in the tree: for all $ 1 \leq j < k $, $ \{v_j, v_{j+1}\} \in E $. - The length of the walk $ k \leq 10^7 $. - The initial color of vertex $ 1 $ is given as $ c_1 $; the squirrel starts there and flips it upon visit. **Objective:** Find a walk $ w $ starting at vertex $ 1 $ such that, for every vertex $ i \in V $, the number of times $ i $ is visited in $ w $ has the same parity as $ 1 - c_i $ (i.e., if $ c_i = -1 $, it must be visited an odd number of times; if $ c_i = 1 $, it must be visited an even number of times — including zero). **Note:** Since the tree is connected and the solution is guaranteed to exist, a valid walk can be constructed via a DFS-like traversal that ensures each pink node is flipped an odd number of times and each black node an even number of times. A standard approach is to perform a DFS from node 1, and upon returning from a subtree, flip the parent if needed — but since the squirrel must traverse edges, a practical method is to use a "Euler Tour" style walk: traverse the tree in DFS order, and whenever backtracking, include the parent again. This ensures every edge is traversed twice (once down, once up), and every non-root node is visited exactly twice (once when going down, once when coming up), while the root is visited once more than its degree. However, since the root (vertex 1) may need an odd number of visits if initially pink, we adjust accordingly. **Formal Output Requirement:** Output a sequence of vertex indices $ v_1, v_2, \dots, v_k $ such that: - $ v_1 = 1 $, - $ \forall j \in [1, k-1] $, $ \{v_j, v_{j+1}\} \in E $, - For each $ i \in V $, the number of times $ i $ appears in the sequence $ \equiv (1 - c_i) \mod 2 $. **Solution Construction (Implicit):** Use a DFS traversal from vertex 1. For each child, recursively traverse the subtree, and upon returning from a child, append the current node again. This ensures that every node (except possibly the root) is visited an even number of times (twice per subtree). The root is visited once initially, and then once for each child return. If the root is initially pink ($ c_1 = -1 $), then the number of visits must be odd — which is naturally satisfied if the root has at least one child (since it will be visited $ 1 + \text{deg}(1) $ times). If the root is black ($ c_1 = 1 $), we need even visits — so if $ \text{deg}(1) $ is odd, we may need to append an extra visit to a neighbor and back (but the problem guarantees a solution exists, and the standard DFS backtracking already ensures parity correctness). Thus, the algorithm is: 1. Build the tree as an adjacency list. 2. Perform a DFS starting at node 1. 3. For each node $ u $, append $ u $ to the walk. 4. For each child $ v $ of $ u $ (in any order), recursively process $ v $, then append $ u $ again after returning. 5. The resulting walk will have the correct parity for all nodes. **Final Output:** The sequence of vertices visited during this DFS-with-backtracking walk. This walk has length at most $ 2n - 1 $, well under $ 10^7 $. --- **Formal Output (as required):** A walk $ w = (v_1, v_2, \dots, v_k) $, where $ v_1 = 1 $, each consecutive pair is adjacent in the tree, and for each vertex $ i $, the number of times $ i $ appears in $ w $ is congruent to $ 1 - c_i \pmod{2} $.