← 返回题目列表

AtCoder · keyence2020_e

E. 双色化

中文机器翻译题面 查看原题

分数: 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