AT_keyence2020_e Bichromization

有一个包含 $N$ 个顶点和 $M$ 条边的连通无向图。第 $i$ 条边（$1 \leq i \leq M$）连接顶点 $U_i$ 和顶点 $V_i$，且为双向边。此外，给定 $N$ 个整数 $D_1, D_2, \ldots, D_N$。 请判断是否存在一种方案，可以为该图的每个顶点分配白色或黑色，并为每条边分配一个 $1$ 到 $10^9$ 之间的整数权值，使得满足以下条件。如果存在，请给出一种满足条件的分配方案。 - 被分配为白色和黑色的顶点都至少有一个。 - 对于每个顶点 $v$（$1 \leq v \leq N$），满足以下条件： - 从顶点 $v$ 出发，经过若干条边，移动到一个与 $v$ 分配颜色不同的顶点时，所需的最小总代价恰好为 $D_v$。 其中，图上的移动代价指的是经过的所有边的权值之和。

输入以如下格式从标准输入读入。 > $N$ $M$ $D_1$ $D_2$ $\ldots$ $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$）为 `W` 表示顶点 $i$ 分配为白色，为 `B` 表示分配为黑色。 - 第 $i+1$ 行（$1 \leq i \leq M$）的 $C_i$ 表示第 $i$ 条边分配的权值（输出为整数）。

## 限制条件 - $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$ - 给定的图是连通的，不包含自环和重边。 - 所有输入值均为整数。 ## 样例解释 1 如输出样例所示进行颜色和权值分配时，例如从顶点 $5$ 出发，经过顶点 $4$ 再到顶点 $2$，可以到达一个与顶点 $5$ 颜色不同的顶点，此时总代价为 $7$，满足条件。对其他顶点也可以验证满足条件。 由 ChatGPT 4.1 翻译