You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Bichromization

题目描述

注：本题和AT评分不同，将采用子任务绑定来评分！

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

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

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

输入格式

第一行两个整数 $N,M$ ，第二行 $N$ 个整数 $D_i$ ，接下来 $M$ 行每行两个整数 $U_i,V_i$ 表示一条边。

$N$ $M$ $D_1$ $D_2$ $...$ $D_N$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$

输出格式

如果无解，输出一行一个整数 $-1$ 。

否则，第一行输出一个只含 $B$ 和 $W$ 的长为 $N$ 的字符串 $S$ ，接下来 $M$ 行每行一个整数 $C_i$ 表示每条边的边权，边的顺序按输入顺序给定。

样例 #1

样例输入 #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

样例 #2

样例输入 #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

样例输入 #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

数据范围

对所有数据，满足：

• $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$

具体子任务评分标准如下：