H - Hit and Away 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 450 点

問題文

N 頂点 M 辺の単純連結無向グラフ G が与えられます。
G の頂点および辺はそれぞれ頂点 1,2,\ldots,N、辺 1,2,\ldots,M と番号づけられており、 辺 i は頂点 U_i と頂点 V_i を結んでいます。
辺で結ばれている頂点の間は双方向に時間 1 で移動することができます。

また、各頂点は安全か危険かのどちらかであり、その状態は S と D のみからなる長さ N の文字列 S によって与えられます。
具体的には、S の i 文字目 (1\leq i\leq N) が S のとき頂点 i は安全であり、D のとき頂点 i は危険です。
ここで、安全な頂点が 2 つ以上、危険な頂点が 1 つ以上あることが保証されます。

危険な頂点 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
  • i\neq j ならば \{ U_i,V_i \}\neq \{ U_j,V_j \}
  • S は S と D のみからなる長さ N の文字列
  • N,M,U_i,V_i はすべて整数
  • G は連結である。
  • 安全な頂点が 2 つ以上存在する。
  • 危険な頂点が 1 つ以上存在する。

入力

入力は以下の形式で標準入力から与えられる。

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

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 であり、このときが最小です。
よって、1 行目に 2 を出力します。

頂点 4 については、頂点 1 \to 頂点 3 \to 頂点 4 \to 頂点 5 と移動するときなどが条件をみたします。
この移動にかかる時間は 3 であり、かかる時間が 2 以下の条件をみたす移動方法がないため、このときが最小です。
よって、2 行目に 3 を出力します。

入力例 2

3 2
1 2
2 3
SSD

出力例 2

3

危険な頂点は頂点 3 です。

頂点 1 \to 頂点 2 \to 頂点 3 \to 頂点 2 と移動するときなどが条件をみたします。
この移動にかかる時間は 3 であり、このときが最小です。
頂点 2 \to 頂点 3 \to 頂点 2 などの移動は、「出発した頂点と異なる」という条件をみたしていないことに注意してください。

Score : 450 points

Problem Statement

You are given a simple connected undirected graph G with N vertices and M edges.
The vertices and edges of G are numbered as vertices 1,2,\ldots,N and edges 1,2,\ldots,M, respectively, and edge i connects vertices U_i and V_i.
You can move bidirectionally between vertices connected by an edge in time 1.

Additionally, each vertex is either safe or dangerous, and this state is given by a string S of length N consisting of S and D.
Specifically, vertex i is safe when the i-th character (1\leq i\leq N) of S is S, and vertex i is dangerous when it is D.
It is guaranteed that there are at least two safe vertices and at least one dangerous vertex.

For each dangerous vertex v, find the following value:

The minimum possible time to start from some safe vertex, pass through v, and move to a safe vertex different from the starting vertex.

Constraints

  • 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, then \{ U_i,V_i \}\neq \{ U_j,V_j \}.
  • S is a string of length N consisting of S and D.
  • N,M,U_i,V_i are all integers.
  • G is connected.
  • There are at least two safe vertices.
  • There is at least one dangerous vertex.

Input

The input is given from Standard Input in the following format:

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M
S

Output

Let K be the number of dangerous vertices in G, and print K lines.
On the i-th line (1\leq i\leq K), print the answer for the i-th dangerous vertex when the dangerous vertices are arranged in ascending order of vertex number.

Sample Input 1

5 5
1 2
1 3
2 3
3 4
4 5
SSDDS

Sample Output 1

2
3

The dangerous vertices are (in ascending order of vertex number) vertices 3 and 4.

For vertex 3, moving from vertex 1 \to vertex 3 \to vertex 2 (for example) satisfies the condition.
The time required for this movement is 2, and this is the minimum.
Therefore, print 2 on the 1st line.

For vertex 4, moving from vertex 1 \to vertex 3 \to vertex 4 \to vertex 5 (for example) satisfies the condition.
The time required for this movement is 3, and there is no way to move that satisfies the condition with time 2 or less, so this is the minimum.
Therefore, print 3 on the 2nd line.

Sample Input 2

3 2
1 2
2 3
SSD

Sample Output 2

3

The dangerous vertex is vertex 3.

Moving from vertex 1 \to vertex 2 \to vertex 3 \to vertex 2 (for example) satisfies the condition.
The time required for this movement is 3, and this is the minimum.
Note that movements such as vertex 2 \to vertex 3 \to vertex 2 do not satisfy the condition that the destination is "different from the starting vertex".