/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
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 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 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 以下
入力
入力は以下の形式で標準入力から与えられる。
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 番目のテストケースについての答えを出力せよ。
入力例 1
3 4 4 1 2 1 4 2 4 2 3 3 xxo xox oxo oxx 1 0 4 oooo 5 5 1 4 2 3 4 5 3 4 2 5 7 oxxxxxx xxoxxxo xxxoxox xoxxoxx oxxxoxx
出力例 1
Yes Yes No
一つ目のテストケースについて、例えば都市 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 にとどまり続けることで条件を満たすことができます。
三つ目のテストケースについて、条件を満たすように移動を繰り返すことはできません。
Score : 450 points
Problem Statement
The Kingdom of AtCoder has N cities, called city 1,2,\dots,N. There are M bidirectional roads connecting pairs of cities, where the i-th road connects cities U_i and V_i. Any pair of cities can be reached from each other by traversing some roads.
In the Kingdom of AtCoder, a week consists of W days. A week proceeds through days 1,2,\dots,W, and the day after day W is day 1.
Each city has certain days of the week that are holidays.
The holiday information for city i is given as a string S_i of length W: if the j-th character of S_i is o, day j is a holiday; if it is x, day j is a weekday.
Takahashi chooses a city he likes and visits it at noon on day 1.
Each night thereafter, he repeatedly chooses to either stay in his current city or move to a city directly connected by a road.
Output Yes if it is possible for him to keep moving so that the city he is in at noon every day is a holiday, and No otherwise.
T test cases are given; solve each of them.
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
- Any pair of cities can be reached from each other by traversing some roads.
- 2 \leq W \leq 10
- T,N,M,U_i,V_i,W are integers.
- S_i is a string of length W consisting of
o,x. - The sum of N over all test cases is at most 10^5.
- The sum of M over all test cases is at most 10^5.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Here, \mathrm{case}_i denotes the input for the i-th test case. Each test case is given in the following format:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M W S_1 S_2 \vdots S_N
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
3 4 4 1 2 1 4 2 4 2 3 3 xxo xox oxo oxx 1 0 4 oooo 5 5 1 4 2 3 4 5 3 4 2 5 7 oxxxxxx xxoxxxo xxxoxox xoxxoxx oxxxoxx
Sample Output 1
Yes Yes No
For the first test case, for example, the condition can be satisfied by repeatedly moving along cities 4 \to 2 \to 1 \to 4 \to 2 \to 1 \to \cdots. Alternatively, the condition can also be satisfied by repeatedly moving along cities 3 \to 2 \to 3 \to 3 \to 2 \to 3 \to \cdots.
For the second test case, the condition can be satisfied by staying in city 1 indefinitely.
For the third test case, it is impossible to keep moving while satisfying the condition.