E - Bichromization 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 900 点

問題文

N 頂点 M 辺の連結な無向グラフがあります。 このグラフの辺 i (1 \leq i \leq M) は頂点 U_i と頂点 V_i を双方向に結んでいます。 また、N 個の整数 D_1, D_2, ..., D_N が与えられます。

このグラフの各頂点に白または黒の色を割り当て、さらに 各辺に 1 以上 10^9 以下の整数の重みを割り当てる方法であって、以下の条件を満たすものが存在するかどうか判定してください。 さらに、存在する場合、そのような割り当てをひとつ求めてください。

  • 白および黒が割り当てられた頂点がそれぞれ少なくとも 1 個以上存在する。
  • 各頂点 v (1 \leq v \leq N) に対して以下の条件が成り立つ。
    • 頂点 v からグラフの辺を通って頂点 v と異なる色が割り当てられた頂点に移動する際にかかる最小のコストはちょうど D_v である。

なお、グラフ上の移動にかかるコストとは、 移動の際に通る辺の重みの和のことです。

制約

  • 2 \leq N \leq 100,000
  • 1 \leq M \leq 200,000
  • 1 \leq D_i \leq 10^9
  • 1 \leq U_i, V_i \leq N
  • 与えられるグラフは連結であり、自己ループや多重辺を持たない。
  • 入力値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M
D_1 D_2 ... D_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

出力

割り当てが不可能である場合、-1 と一行に出力せよ。

可能である場合、 割り当て方をひとつ、 以下の形式で出力せよ。

S
C_1
C_2
\vdots
C_M

ただし、

  • 1 行目の出力 S は長さ N の文字列とせよ。 その i 番目 (1 \leq i \leq N) の文字は、頂点 i に白色を割り当てる場合は W とし、黒色を割り当てる場合は B とせよ。
  • i + 1 行目 (1 \leq i \leq M) の出力 C_i は辺 i に割り当てる重みとせよ（整数として出力すること）。

入力例 1

5 5
3 4 3 5 7
1 2
1 3
3 2
4 2
4 5

出力例 1

BWWBB
4
3
1
5
2

出力例のように色と重みを割り当てた場合、たとえば頂点 5 からグラフの辺を通って頂点 5 と異なる色が割り当てられた頂点に最小のコストで移動するには、 頂点 5 \to 頂点 4 \to 頂点 2 と移動すればよく、この移動のコストは 7 となるので、条件を満たします。 他の頂点についても条件を満たすことが確かめられます。

入力例 2

5 7
1 2 3 4 5
1 2
1 3
1 4
2 3
2 5
3 5
4 5

出力例 2

-1

入力例 3

4 6
1 1 1 1
1 2
1 3
1 4
2 3
2 4
3 4

出力例 3

BBBW
1
1
1
2
1
1

Score : 900 points

Problem Statement

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.

  • There is at least one vertex assigned white and at least one vertex assigned black.
  • For each vertex v (1 \leq v \leq N), the following holds.
    • 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.

Here, the cost of traversing the edges is the sum of the weights of the edges traversed.

Constraints

  • 2 \leq N \leq 100,000
  • 1 \leq M \leq 200,000
  • 1 \leq D_i \leq 10^9
  • 1 \leq U_i, V_i \leq N
  • The given graph is connected and has no self-loops or multiple edges.
  • All values in input are integers.

Input

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

Output

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,

  • the first line should contain the string S of length N. Its i-th character (1 \leq i \leq N) should be W if Vertex i is assigned white and B if it is assigned black.
  • The (i + 1)-th line (1 \leq i \leq M) should contain the integer weight C_i assigned to Edge i.

Sample Input 1

5 5
3 4 3 5 7
1 2
1 3
3 2
4 2
4 5

Sample Output 1

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.

Sample Input 2

5 7
1 2 3 4 5
1 2
1 3
1 4
2 3
2 5
3 5
4 5

Sample Output 2

-1

Sample Input 3

4 6
1 1 1 1
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 3

BBBW
1
1
1
2
1
1