Optimal Shop Location in B City

B City is divided into two regions: the city center and the suburbs. The two regions are separated by a ring road. The ring road is represented as the unique cycle in a connected unicyclic graph with n vertices and n edges. Every vertex i has a traffic value p_i and if a shop is opened at vertex i the profit is p_i \times k (with \(k\) being a constant). However, any edge’s two endpoints cannot both have shops. Jim wants to maximize his total profit. Help him decide at which vertices to open a shop.

Note: The graph is unicyclic, i.e. it contains exactly one simple cycle (the ring road) and all other parts are tree branches (representing the suburbs attached to the ring road). In the cycle, any two vertices have exactly two simple paths between them. Your task is to select a set of vertices (locations to open shops) such that no two adjacent vertices (by an edge) are both chosen and the total profit is maximized. In addition, output the list of vertices (in increasing order) where shops should be opened.

Input details: The first line contains two integers n and k. The second line contains n integers, where the i-th integer denotes p_i. Each of the next n lines contains two integers u and v that describe an edge of the graph.

Output details: On the first line, output the maximum total profit. On the second line, output the selected vertex indices (in increasing order) separated by a space.

All formulas are rendered in LaTeX format. For example, the profit for vertex i is given by: \(p_i\times k\).

inputFormat

The input begins with a line containing two integers n and k (the number of vertices and the constant multiplier). The second line contains n integers: p₁, p₂, …, p_n (the traffic values for each vertex). The next n lines each contain two integers u and v indicating there is an edge between vertices u and v.

outputFormat

Output two lines. The first line should contain the maximum profit. The second line should contain the list of vertex indices (in increasing order) where Jim should open shops so that the profit is maximized.

sample

5 10
1 2 3 4 5
1 2
2 3
3 4
4 5
5 1

80
2 4