【25CSPS提高组】（replace）

题目描述

小 W 是一名喜欢语言学的算法竞赛选手。在语言学中，谐音替换是指将原有的字词替换为读音相同或相近的字词。小 W 发现，谐音替换的过程可以用字符串来进行描述。具体地，小 W 将谐音替换定义为以下字符串问题：

给定 (n) 个字符串二元组，第 (i)（(1 \leq i \leq n)）个字符串二元组为 ((s_{i,1}, s_{i,2}))，满足 (|s_{i,1}| = |s_{i,2}|)，其中 (|s|) 表示字符串 (s) 的长度。

对于字符串 (s)，定义 (s) 的替换如下：

• 对于 (s) 的某个子串 (y)，若存在 (1 \leq i \leq n) 满足 (y = s_{i,1})，则将 (y) 替换为 (y' = s_{i,2})。具体地，设 (s = x + y + z)，其中 (x) 和 (z) 可以为空，“+” 表示字符串拼接，则 (s) 的替换将得到字符串 (s' = x + y' + z)。

小 W 提出了 (q) 个问题，第 (j)（(1 \leq j \leq q)）个问题会给定两个不同的字符串 (t_{j,1}, t_{j,2})，她想知道有多少种字符串 (t_{j,1}) 的替换能够得到字符串 (t_{j,2})。两种 (s) 的替换不同当且仅当子串 (y) 的位置不同或用于替换的二元组 ((s_{i,1}, s_{i,2})) 不同，即 (x, z) 不同或 (i) 不同。

你需要回答小 W 提出的所有问题。

输入格式

输入的第一行包含两个正整数 (n, q)，分别表示字符串二元组的数量和小 W 提出的问题的数量。

输入的第 (i+1)（(1 \leq i \leq n)）行包含两个字符串 (s_{i,1}, s_{i,2})，表示第 (i) 个字符串二元组。

输入的第 (j+n+1)（(1 \leq j \leq q)）行包含两个字符串 (t_{j,1}, t_{j,2})，表示小 W 提出的第 (j) 个问题。

输出格式

输出 (q) 行，其中第 (j)（(1 \leq j \leq q)）行包含一个非负整数，表示替换后得到字符串 (t_{j,2}) 的字符串 (t_{j,1}) 的替换的数量。

输入输出样例

样例 1

输入：

4 2
xabcx xadex
ab cd
bc de
aa bb
xabcx xadex
aaaa bbbb

输出：

2
0

样例 1 解释

对于小 W 的第一个询问，共有 2 种 (t_{1,1}) 的替换能够得到 (t_{1,2})：

1. 令 (x, z) 均为空串，(y = \texttt{xabcx})，(i = 1)，则 (y' = \texttt{xadex})，替换后得到 (\texttt{xadex})；
2. 令 (x = \texttt{xa})，(y = \texttt{bc})，(z = \texttt{x})，(i = 3)，则 (y' = \texttt{de})，替换后得到 (\texttt{xadex})。

样例 2

输入：

3 4
a b
b c
c d
aa bb
aa b
a c
b a

输出：

0
0
0
0

样例 3

见选手目录下的 replace/replace3.in 与 replace/replace3.ans。该样例满足测试点 11, 12 的约束条件。

样例 4

见选手目录下的 replace/replace4.in 与 replace/replace4.ans。该样例满足测试点 15, 16 的约束条件。

数据范围

设 (L_1 = \sum_{i=1}^{n} |s_{i,1}| + |s_{i,2}|)，(L_2 = \sum_{j=1}^{q} |t_{j,1}| + |t_{j,2}|)。

对于所有测试数据，保证：

• (1 \leq n, q \leq 2 \times 10^5)；
• (2 \leq L_1, L_2 \leq 5 \times 10^6)；
• 对于所有 (1 \leq i \leq n)，(s_{i,1}, s_{i,2}) 均仅包含小写英文字母，且 (|s_{i,1}| = |s_{i,2}|)；
• 对于所有 (1 \leq j \leq q)，(t_{j,1}, t_{j,2}) 均仅包含小写英文字母，且 (t_{j,1} \neq t_{j,2})。

特殊性质 A：(q = 1)。

特殊性质 B：定义字符串 (s) 为特别的，当且仅当字符串 (s) 仅包含字符 a 和 b，且字符 b 在 (s) 中出现恰好一次。对于所有 (1 \leq i \leq n)，(s_{i,1}, s_{i,2}) 均为特别的，且对于所有 (1 \leq j \leq q)，(t_{j,1}, t_{j,2}) 均为特别的。