小红拿到了一个图,其由 个顶点、条边组成。 这个图上面的一些点被染成了红色。 小红有一个能力:她每次可以点击一个红色的顶点,并将和这个顶点相邻的红色连通块的所有红色顶点全部标记。 当两个红色顶点有一条边相连时,这两个红色顶点被称为连通的。另外,若a和b连通且b和c连通,那么a和c也是连通的。 小红想知道自己至少要点击多少次,可以把所有红色的顶点全部标记。 你能告诉她点击的次数吗?并请你输出一个点击的方案,如果有多个方案合法,请你输出一个字典序最小的方案。 注:字典序的定义:两个不同方案的字典序比较:对于从左到右数第一个不同的数,哪个方案最小,那么它的字典序最小。 例如:方案[1,4,5]和方案[1,3,6]相比,后者更小。因为第一个出现的不同的数是第二个数,43。
输入描述:
第一行输出两个正整数 和 ,用空格隔开。分别代表顶点数和边数。第二行输入一个长度为 的字符串,代表每个顶点的染色情况。第 个字符为'R'代表第 个点被染成红色,为'W'代表未被染色。接下来的 行,每行两个正整数 和 ,代表 和 有一条无向边相连。不保证图是整体连通的。不保证没有重边和自环。数据范围:
输出描述:
第一行输出一个正整数 ,代表小红的点击次数。第二行输出 个正整数,用空格隔开,代表小红点击的顺序。
示例1
输入
5 5
RRRWR
3 4
3 1
2 5
5 5
4 5
说明
可以发现,共有2个红色连通块:{1,3}和{2,5}。只需要点击2次即可,字典序最小的方案是[1,2]
加载中...