AT_tenka1_2012_qualA_3 敵対的引用

[problemUrl]: https://atcoder.jp/contests/tenka1-2012-qualA/tasks/tenka1_2012_qualA_3 $ N $ 個のグループがあります。 それぞれのグループには、「group$ 1 $」から「group$ N $」までの名前がついています。 ある日、あるグループがあるグループを呼び、そして、発言を引用するということが繰り返されました。 group$ A $ が group$ B $ に対して攻撃的であるとします。そのとき - group$ A $ は group$ B $ を呼ぶとき、グループの名前のうしろに `w` をつけ、「group$ B $w」 と発言します。 - group$ A $ は group$ B $ の発言を引用するとき、group$ B $ の発言をダブルクォーテーション (`"`) で囲んで引用し、うしろに `ww` をつけて発言します。 また、group$ A $ が group$ B $ に対して攻撃的でないとします。そのとき - group$ A $ は group$ B $ を呼ぶとき、「group$ B $」 と発言します。 - group$ A $ は group$ B $ の発言を引用するとき、group$ B $ の発言をダブルクォーテーション (`"`) で囲んで引用し、うしろには何もつけずに発言します。 例えば、group2 が group1 に対して攻撃的であるとき、group2 は `group1w` と発言します。 さらに、group3 が group2 に対して攻撃的であるとき、group3 は `"group1w"ww` と発言します。 また、group2 が group3 に対して攻撃的でないとき、group2 は `group3` と発言します。 さらに、group1 が group2 に対して攻撃的でないとき、group1 は `"group3"` と発言します。 group$ A $ が group$ B $ に攻撃的だが、group$ B $ がgroup$ A $ に攻撃的ではないということもあります。 また、自虐的なグループ、つまり自分自身に対して攻撃的なグループもあります。 ある $ 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\ \leq\ N\ \leq\ 100 $ ) のみ正解すると、$ 100 $ 点満点に対して部分点として $ 50 $ 点が与えられる。 発言 $ s $ を行った可能性のあるグループの数を、標準出力に $ 1 $ 行で出力せよ。 なお、行の終端には改行が必要である。

N/A

N/A