配点 : $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$ である。
• 頂点 $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$ に割り当てる重みとせよ（整数として出力すること）。

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

BWWBB
4
3
1
5
2

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

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