AT_abc429_e [ABC429E] Hit and Away

$ 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 $ を経由し、 **出発した頂点と異なる** 安全な頂点へ移動するのにかかる時間としてあり得る最小値

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 番目に来る頂点についての答えを出力せよ。

### Sample Explanation 1 危険な頂点は（頂点番号について昇順に）頂点 $ 3 $ と $ 4 $ です。 頂点 $ 3 $ については、頂点 $ 1 $ $ \to $ 頂点 $ 3 $ $ \to $ 頂点 $ 2 $ と移動するときなどが条件をみたします。 この移動にかかる時間は $ 2 $ であり、このときが最小です。 よって、 $ 1 $ 行目に $ 2 $ を出力します。 頂点 $ 4 $ については、頂点 $ 1 $ $ \to $ 頂点 $ 3 $ $ \to $ 頂点 $ 4 $ $ \to $ 頂点 $ 5 $ と移動するときなどが条件をみたします。 この移動にかかる時間は $ 3 $ であり、かかる時間が $ 2 $ 以下の条件をみたす移動方法がないため、このときが最小です。 よって、 $ 2 $ 行目に $ 3 $ を出力します。 ### Sample Explanation 2 危険な頂点は頂点 $ 3 $ です。 頂点 $ 1 $ $ \to $ 頂点 $ 2 $ $ \to $ 頂点 $ 3 $ $ \to $ 頂点 $ 2 $ と移動するときなどが条件をみたします。 この移動にかかる時間は $ 3 $ であり、このときが最小です。 頂点 $ 2 $ $ \to $ 頂点 $ 3 $ $ \to $ 頂点 $ 2 $ などの移動は、「出発した頂点と異なる」という条件をみたしていないことに注意してください。 ### 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 $ - $ 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 $ つ以上存在する。