Score : 900 points
We have a connected undirected graph with N vertices and M edges. Edge i in this graph (1 \leq i \leq M) connects Vertex U_i and Vertex V_i bidirectionally. We are additionally given N integers D_1, D_2, ..., D_N.
Determine whether the conditions below can be satisfied by assigning a color - white or black - to each vertex and an integer weight between 1 and 10^9 (inclusive) to each edge in this graph. If the answer is yes, find one such assignment of colors and integers, too.
Here, the cost of traversing the edges is the sum of the weights of the edges traversed.
Input is given from Standard Input in the following format:
N M D_1 D_2 ... D_N U_1 V_1 U_2 V_2 \vdots U_M V_M
If there is no assignment satisfying the conditions, print a single line containing -1
.
If such an assignment exists, print one such assignment in the following format:
S C_1 C_2 \vdots C_M
Here,
W
if Vertex i is assigned white and B
if it is assigned black.5 5 3 4 3 5 7 1 2 1 3 3 2 4 2 4 5
BWWBB 4 3 1 5 2
Assume that we assign the colors and integers as the sample output, and let us consider Vertex 5, for example. To travel from Vertex 5, which is assigned black, to a vertex that is assigned white with the minimum cost, we should make these moves: Vertex 5 \to Vertex 4 \to Vertex 2. The total cost of these moves is 7, which satisfies the condition. We can also verify that the condition is satisfied for other vertices.
5 7 1 2 3 4 5 1 2 1 3 1 4 2 3 2 5 3 5 4 5
-1
4 6 1 1 1 1 1 2 1 3 1 4 2 3 2 4 3 4
BBBW 1 1 1 2 1 1