C - 敵対的引用
解説
/ 
入力は以下の形式で標準入力から与えられる。
グループの数が少ない入力 ( 1 \leq N \leq 100 ) のみ正解すると、100 点満点に対して部分点として 50 点が与えられる。
発言 s を行った可能性のあるグループの数を、標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。
/ 
実行時間制限: 2 sec / メモリ制限: 64 MB
問題文
N 個のグループがあります。
それぞれのグループには、「group1」から「groupN」までの名前がついています。
ある日、あるグループがあるグループを呼び、そして、発言を引用するということが繰り返されました。
groupA が groupB に対して攻撃的であるとします。そのとき
- groupA は groupB を呼ぶとき、グループの名前のうしろに
wをつけ、「groupBw」 と発言します。 - groupA は groupB の発言を引用するとき、groupB の発言をダブルクォーテーション (
") で囲んで引用し、うしろにwwをつけて発言します。
また、groupA が groupB に対して攻撃的でないとします。そのとき
- groupA は groupB を呼ぶとき、「groupB」 と発言します。
- groupA は groupB の発言を引用するとき、groupB の発言をダブルクォーテーション (
") で囲んで引用し、うしろには何もつけずに発言します。
例えば、group2 が group1 に対して攻撃的であるとき、group2 は group1w と発言します。
さらに、group3 が group2 に対して攻撃的であるとき、group3 は "group1w"ww と発言します。
また、group2 が group3 に対して攻撃的でないとき、group2 は group3 と発言します。
さらに、group1 が group2 に対して攻撃的でないとき、group1 は "group3" と発言します。
groupA が groupB に攻撃的だが、groupB がgroupA に攻撃的ではないということもあります。
また、自虐的なグループ、つまり自分自身に対して攻撃的なグループもあります。
ある 1 つの発言が与えられるので、その発言をしそうなグループの総数を答えてください。
入力
N M a_1 b_1 a_2 b_2 : : a_M b_M s
- 1 行目は、グループの数を表す整数 N (1 \leq N \leq 10^5) , 敵対的関係を表す整数 M (1 \leq M \leq 10000) が与えられる。
- 2 行目から M 行は、グループの敵対関係が与えられる。
- a_i, b_i (1 \leq a_i, b_i \leq N) はグループ a_i がグループ b_i に対して攻撃的であることを表す。
- i \neq j ならば、 a_i \neq a_j または b_i \neq b_j である。
- M+2 行目は、あるグループの発言 s が与えられる。
- s の文字列長は 300 以下である。
- 少なくとも 1 グループは発言を行った可能性がある。
部分点
出力
なお、行の終端には改行が必要である。
入力例 1
3 6 1 2 1 3 2 1 2 3 3 1 3 2 "group1w"ww
出力例 1
3
group1wと発言したのは group2 または group3 である。- group2 が
group1wと発言した場合、"group1w"wwと発言したのは group1 または group3 である。 - group3 が
group1wと発言した場合、"group1w"wwと発言したのは group1 または group2 である。 - よって、発言
"group1w"wwを行った可能性のあるグループは、 group1, group2, group3 の 3 グループである。
入力例 2
3 2 1 2 2 3 "group3w"
出力例 2
2
- この発言を行った可能性のあるグループは、 group2, group3 の 2 グループである。
入力例 3
3 1 1 1 ""group1w"ww"ww
出力例 3
1
- 自分自身のグループを呼ぶ場合や、自分自身のグループの発言を引用する場合もある。