给定一个简单连通无向图 $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 翻译