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 翻译