AT_abc456_e [ABC456E] Endless Holidays

AtCoder 王国には $ N $ 個の都市があり、それぞれ都市 $ 1,2,\dots,N $ と呼ばれています。 また都市同士を双方向に結ぶ $ M $ 本の道路があり、 $ i $ 番目の道路は都市 $ U_i $ と都市 $ V_i $ を結んでいます。 どの都市間もいくつかの道路を辿ることで行き来可能です。 AtCoder 王国では一週間が $ W $ 日からなります。 一週間は曜日 $ 1,2,\dots,W $ と進んでいき、曜日 $ W $ の次の日は曜日 $ 1 $ に戻ります。 都市ごとにいくつかの曜日が休日となっています。 都市 $ i $ の休日の情報は長さ $ W $ の文字列 $ S_i $ で与えられ、 $ S_i $ の $ j $ 文字目が `o` のとき曜日 $ j $ が休日であることを、`x` のとき曜日 $ j $ が平日であることを意味します。 高橋君は曜日 $ 1 $ の日の昼に、好きな都市を選んでそこを訪問します。 それ以降毎日夜に一度、今いる都市にとどまるか、道路で直接結ばれた都市のいずれかに移動することを繰り返します。 毎日昼の時点でいる都市が休日であるように移動を続けることが可能ならば `Yes` を、不可能ならば `No` を出力してください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ ここで $ \mathrm{case}_i $ は $ i $ 番目のテストケースの入力を意味する。各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_M $ $ V_M $ $ W $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについての答えを出力せよ。

### Sample Explanation 1 一つ目のテストケースについて、例えば都市 $ 4 \to 2 \to 1 \to 4 \to 2 \to 1 \to \cdots $ と移動を繰り返すことで条件を満たすことができます。 他にも都市 $ 3 \to 2 \to 3 \to 3 \to 2 \to 3 \to \cdots $ と移動を繰り返すことでも条件を満たすことができます。 二つ目のテストケースについて、都市 $ 1 $ にとどまり続けることで条件を満たすことができます。 三つ目のテストケースについて、条件を満たすように移動を繰り返すことはできません。 ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 1 \leq N \leq 10^5 $ - $ N-1 \leq M \leq 10^5 $ - $ 1 \leq U_i \lt V_i \leq N $ - どの都市間もいくつかの道路を辿ることで行き来可能である - $ 2 \leq W \leq 10 $ - $ T,N,M,U_i,V_i,W $ は整数 - $ S_i $ は `o`, `x` からなる長さ $ W $ の文字列 - 全てのテストケースにおける $ N $ の総和は $ 10^5 $ 以下 - 全てのテストケースにおける $ M $ の総和は $ 10^5 $ 以下