#P17988. Fix the Coloring

Fix the Coloring

Fix the Coloring

题目描述

给定一个有 nn 个顶点、mm 条边的简单无向图。每个顶点最初为黑色 B 或白色 W。你可以选择任意一些顶点,将它们重新染为红色 R;其他顶点必须保留原来的颜色。

判断能否得到满足下列条件的染色,并在可行时输出一种方案:

  • 所有两端都是红色的边,恰好组成一个团的边集。没有这种边也允许。
  • 其余每条边的两个端点颜色不同。

这里团指任意两个不同顶点之间都有边的顶点集合。红色顶点可以包含不与其他红色顶点相邻的孤立红点;这些点不属于上述非平凡红团。不能出现两个分离的非平凡红团。

输入格式

第一行一个整数 tt,表示测试用例数。

每个测试用例的第一行包含 n,mn,m。第二行是长度为 nn 的字符串,由 B 和 W 组成,表示初始颜色。

接下来 mm 行,每行两个整数 u,vu,v,表示一条无向边。顶点编号为 11 到 nn,无自环、无重边。图不一定连通。

输出格式

每个测试用例无解时输出一行 NO。有解时先输出一行 YES,再输出长度为 nn 的字符串,表示合法染色。存在多种方案时可以输出任意一种。

数据范围

1≤t≤10001\le t\le1000,1≤n,m≤30001\le n,m\le3000。所有测试用例的 nn 之和不超过 30003000,mm 之和也不超过 30003000。

样例输入

2
6 7
BBBWBB
1 2
2 3
3 1
2 4
2 5
4 5
5 6
6 7
BBBBBB
1 2
2 3
3 1
2 4
2 5
4 5
5 6

样例输出

YES
RRRWBR
NO

第一组可以将顶点 1,2,31,2,3 所在的团以及顶点 66 染红。