#P17988. Fix the Coloring
Fix the Coloring
Fix the Coloring
题目描述
给定一个有 个顶点、 条边的简单无向图。每个顶点最初为黑色 B 或白色 W。你可以选择任意一些顶点,将它们重新染为红色 R;其他顶点必须保留原来的颜色。
判断能否得到满足下列条件的染色,并在可行时输出一种方案:
- 所有两端都是红色的边,恰好组成一个团的边集。没有这种边也允许。
- 其余每条边的两个端点颜色不同。
这里团指任意两个不同顶点之间都有边的顶点集合。红色顶点可以包含不与其他红色顶点相邻的孤立红点;这些点不属于上述非平凡红团。不能出现两个分离的非平凡红团。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例的第一行包含 。第二行是长度为 的字符串,由 B 和 W 组成,表示初始颜色。
接下来 行,每行两个整数 ,表示一条无向边。顶点编号为 到 ,无自环、无重边。图不一定连通。
输出格式
每个测试用例无解时输出一行 NO。有解时先输出一行 YES,再输出长度为 的字符串,表示合法染色。存在多种方案时可以输出任意一种。
数据范围
,。所有测试用例的 之和不超过 , 之和也不超过 。
样例输入
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
第一组可以将顶点 所在的团以及顶点 染红。