分数: 900 点
问题陈述
我们有一个连通的无向图 N 顶点和 M 边缘。 边缘 i 在此图中(1 \leq i \leq M) 连接顶点 U_i 和顶点 V_i 双向。 我们还额外给出了 N 整数 D_1, D_2, ..., D_N.
通过为每个顶点分配颜色(白色或黑色)以及之间的整数权重来确定是否可以满足以下条件 1 和 10^9 (含)到该图中的每条边。 如果答案是肯定的,也找到一个这样的颜色和整数分配。
- 至少有一个顶点指定为白色,并且至少有一个顶点指定为黑色。
- 对于每个顶点 v (1 \leq v \leq N),以下内容成立。
- 从 Vertex 出发的最低旅行成本 v 分配给与 Vertex 颜色不同的顶点 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
在这里,
- 第一行应包含字符串 S 长度 N。其 i- 第一个字符 (1 \leq i \leq N)应该是
W如果顶点 i 被指定为白色并且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
假设我们将颜色和整数指定为样本输出,并让我们考虑 Vertex 例如 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