C - 敵対的引用

Time Limit: 2 sec / Memory Limit: 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 \leq N \leq 100 ) のみ正解すると、100 点満点に対して部分点として 50 点が与えられる。

出力

発言 s を行った可能性のあるグループの数を、標準出力に 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
  • 自分自身のグループを呼ぶ場合や、自分自身のグループの発言を引用する場合もある。

Source Name

天下一プログラマーコンテスト2012 予選A