AT_tenka1_2012_qualA_3 敵対的引用

你有 $N$ 个小组，每个小组的名字从「group1」到「group$N$」。这些小组之间有时会相互呼叫并引用彼此的发言。 当 group$A$ 对 group$B$ 是攻击性时： - group$A$ 呼叫 group$B$ 时，会在名字末尾加一个 `w`，变成「group$B$w」。 - group$A$ 引用 group$B$ 的发言时，会用双引号把发言内容括起来，并在后面加上 `ww`，形成 `"...ww"`。 当 group$A$ 对 group$B$ 没有攻击性时： - 呼叫 group$B$ 时，直接使用「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$ 攻击，甚至会有组自对自身攻击的情况。 给你一个发言，请判断哪些小组可能说出了这句话，并给出可能的小组数量。

输入第一行包含两个整数 $N$ 和 $M$，分别表示小组的总数和敌对关系的数量。这一行的格式是： ``` N M ``` 之后的 $M$ 行，每行两个整数 $a_i$ 和 $b_i$，表示小组 $a_i$ 对小组 $b_i$ 是攻击性的，其格式为： ``` a_1 b_1 a_2 b_2 ... a_M b_M ``` 接下来最后一行是一个字符串 $s$，代表某小组的发言内容： ``` s ```

输出一个整数，表示可能发出该发言的小组数量。

- $1 \leq N \leq 10^5$ - $1 \leq M \leq 10000$ - $1 \leq a_i, b_i \leq N$ - 字符串 $s$ 的长度不超过 $300$ - 至少有一个小组可能发出的发言 在小组数量小的情况下（$1 \leq N \leq 100$），正确解答这些情况即可获得部分分数（50分）。 **本翻译由 AI 自动生成**