题目描述

$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$ である。

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

输入格式

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

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

题目大意

你有一个 $N$ 个点 $M$ 条边的无向连通图，第 $i$ 个点有点权 $D_i$。你现在要给每个点染上黑白两种颜色，以及给每条边一个 $[1,10^9]$ 之间的整数边权，使得：

• 白点和黑点都要出现。
• 点 $i$ 到和它颜色不一样的点的最短路为 $D_i$。

请判断是否有解，如果有要输出方案，否则输出-1。

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

BWWBB
4
3
1
5
2

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

提示

制約

• $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$
• 与えられるグラフは連結であり、自己ループや多重辺を持たない。
• 入力値はすべて整数である。

Sample Explanation 1

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