问题 C: [CSP-S 2025] 谐音替换

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

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

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

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

小 W 提出了 $q$ 个问题，第 $j$ ($1\le j\le 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 提出的所有问题。

说明/提示

【数据范围】

设 $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\le n,q\le 2\times 10^5$;
• $2\le L_1,L_2\le 5\times 10^6$;
• 对于所有 $1\le i\le n$, $s_{i,1},s_{i,2}$ 均仅包含小写英文字母，且 $|s_{i,1}|=|s_{i,2}|$;
• 对于所有 $1\le j\le q$, $t_{j,1},t_{j,2}$ 均仅包含小写英文字母，且 $t_{j,1}\ne t_{j,2}$。

特殊性质 A：$q=1$。

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

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

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

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

样例输入1：
4 2
xabcx xadex
ab cd
bc de
aa bb
xabcx xadex
aaaa bbbb
样例输出1：
2
0

样例输入2：
3 4
a b
b c
c d
aa bb
aa b
a c
b a
样例输出2：
0
0
0
0