← 返回题目列表

AtCoder · abc429_e

H. 击中并离开

中文机器翻译题面 查看原题

分数: 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 不满足目的地“与起始顶点不同”的条件。