分数: 450 点
问题陈述
给你一个简单的连通无向图 G 与 N 顶点和 M 边缘。
的顶点和边 G 被编号为顶点 1,2,\ldots,N 和边缘 1,2,\ldots,M分别是
和边缘 i 连接顶点 U_i 和 V_i.
您可以在由时间边连接的顶点之间双向移动 1.
此外,每个顶点要么是安全的,要么是危险的,并且这个状态由一个字符串给出 S 长度 N 组成 S 和 D.
具体来说,顶点 i 是安全的 i- 第一个字符 (1\leq i\leq N) of S is S,和顶点 i 是危险的 D.
保证至少有两个安全顶点和至少一个危险顶点。
对于每个危险顶点 v,找到以下值:
从某个安全顶点开始,经过的最短可能时间 v,并移动到安全顶点 与起始顶点不同.
约束
- 3\leq N\leq 2\times 10^5
- N-1\leq M\leq 2\times 10^5
- 1\leq U_i,V_i\leq N
- U_i\neq V_i
- If i\neq j,那么 \{ U_i,V_i \}\neq \{ U_j,V_j \}.
- S 是一个长度为的字符串 N 组成
S和D. - N,M,U_i,V_i 均为整数。
- G 已连接。
- 至少有两个安全顶点。
- 至少有一个危险顶点。
输入
输入由标准输入按以下格式给出:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M S
输出
让 K 是危险顶点的数量 G,并打印 K 行。
关于 i第行 (1\leq i\leq K),打印答案 i-当危险顶点按顶点编号升序排列时的第一个危险顶点。
示例输入 1
5 5 1 2 1 3 2 3 3 4 4 5 SSDDS
示例输出 1
2 3
危险顶点为(按顶点编号升序排列)个顶点 3 和 4.
对于顶点 3,从顶点移动 1 \to 顶点 3 \to 顶点 2 (例如)满足条件。
该运动所需的时间为 2,这是最小值。
因此,打印 2 上 1st 线。
对于顶点 4,从顶点移动 1 \to 顶点 3 \to 顶点 4 \to 顶点 5 (例如)满足条件。
该运动所需的时间为 3,并且没有办法随时间移动满足条件 2 或更少,所以这是最小值。
因此,打印 3 上 2第一行。
示例输入 2
3 2 1 2 2 3 SSD
示例输出 2
3
危险顶点是顶点 3.
从顶点移动 1 \to 顶点 2 \to 顶点 3 \to 顶点 2 (例如)满足条件。
该运动所需的时间为 3,这是最小值。
请注意,顶点等运动 2 \to 顶点 3 \to 顶点 2 不满足目的地“与起始顶点不同”的条件。