AT_abc429_e [ABC429E] Hit and Away

给定一个简单连通无向图 $G$，有 $N$ 个顶点和 $M$ 条边。 图中的顶点及边分别编号为 $1,2,\ldots,N$ 和 $1,2,\ldots,M$。第 $i$ 条边连接顶点 $U_i$ 和 $V_i$。 你可以在时间 $1$ 内在一条边连接的两个顶点之间双向移动。 此外，每个顶点要么是安全的，要么是危险的，这一状态由长度为 $N$ 的字符串 $S$ 给出，字符串由 `S` 和 `D` 组成。 具体地，当 $S$ 的第 $i$ 个字符（$1 \leq i \leq N$）为 `S` 时，第 $i$ 个顶点是安全顶点；为 `D` 时，该顶点是危险顶点。 保证至少有两个安全顶点，且至少有一个危险顶点。 对于每个危险顶点 $v$，求以下数值： > 从某一个安全顶点出发，经过 $v$，再移动到另一个**不同于出发点**的安全顶点的最小可能时间。

输入以如下格式从标准输入给出： > $N$ $M$ > $U_1$ $V_1$ > $U_2$ $V_2$ > $\vdots$ > $U_M$ $V_M$ > $S$

设 $G$ 中危险顶点总数为 $K$，输出 $K$ 行。 第 $i$ 行（$1\leq i\leq K$）输出按照顶点编号升序排列的第 $i$ 个危险顶点的答案。

### 样例解释 1 危险顶点按编号升序分别为 $3$ 和 $4$。 对于顶点 $3$，从顶点 $1\to 3\to 2$（例如）可以满足条件。 所需时间为 $2$，且这是最小值。 因此，第 $1$ 行输出 $2$。 对于顶点 $4$，从顶点 $1\to 3\to 4\to 5$（例如）可以满足条件。 所需时间为 $3$，且不存在比 $3$ 更小的方案。 因此，第 $2$ 行输出 $3$。 ### 样例解释 2 危险顶点是顶点 $3$。 从顶点 $1\to 2\to 3\to 2$（例如）可以满足条件。 所需时间为 $3$，且这是最小值。 注意，从顶点 $2\to 3\to 2$ 等方案不满足“终点是与起点不同的安全顶点”的条件。 # 数据范围 - $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$ - 如果 $i\neq j$，则 $\{U_i,V_i\}\neq \{U_j,V_j\}$。 - $S$ 是由 `S` 和 `D` 组成的长度为 $N$ 的字符串。 - $N,M,U_i,V_i$ 均为整数。 - $G$ 是连通图。 - 至少有两个安全顶点。 - 至少有一个危险顶点。 由 ChatGPT 5 翻译