{"raw_statement":[{"iden":"problem statement","content":"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$.\nDetermine 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.\n\n*   There is at least one vertex assigned white and at least one vertex assigned black.\n*   For each vertex $v$ ($1 \\leq v \\leq N$), the following holds.\n    *   The minimum cost to travel from Vertex $v$ to a vertex whose color assigned is different from that of Vertex $v$ by traversing the edges is equal to $D_v$.\n\nHere, the cost of traversing the edges is the sum of the weights of the edges traversed."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 100,000$\n*   $1 \\leq M \\leq 200,000$\n*   $1 \\leq D_i \\leq 10^9$\n*   $1 \\leq U_i, V_i \\leq N$\n*   The given graph is connected and has no self-loops or multiple edges.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$D_1$ $D_2$ $...$ $D_N$\n$U_1$ $V_1$\n$U_2$ $V_2$\n$\\vdots$\n$U_M$ $V_M$"},{"iden":"sample input 1","content":"5 5\n3 4 3 5 7\n1 2\n1 3\n3 2\n4 2\n4 5"},{"iden":"sample output 1","content":"BWWBB\n4\n3\n1\n5\n2\n\nAssume 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."},{"iden":"sample input 2","content":"5 7\n1 2 3 4 5\n1 2\n1 3\n1 4\n2 3\n2 5\n3 5\n4 5"},{"iden":"sample output 2","content":"\\-1"},{"iden":"sample input 3","content":"4 6\n1 1 1 1\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4"},{"iden":"sample output 3","content":"BBBW\n1\n1\n1\n2\n1\n1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}