当前没有测试数据。

本题暂未上传测试数据，目前仅供阅读与练习。

本站练习请使用标准输入/输出；原卷中的文件名仅作原始资料参考。

题目描述

给定 $n$ 个字符串二元组 $(s_{i,1},s_{i,2})$，满足 $|s_{i,1}|=|s_{i,2}|$。

对字符串 $s$ 进行一次替换：选择它的一个子串 $y$，并选择满足 $y=s_{i,1}$ 的二元组，将这个子串替换为 $y'=s_{i,2}$。也就是说，若 $s=x+y+z$，则替换后为 $s'=x+y'+z$，其中 $x,z$ 可以为空，$+$ 表示拼接。

共有 $q$ 个询问，每个询问给出两个不同的字符串 $t_{j,1},t_{j,2}$，求有多少种对 $t_{j,1}$ 的一次替换，能够得到 $t_{j,2}$。

两种替换不同，当且仅当被替换子串的位置不同，或采用的二元组下标 $i$ 不同。

输入格式

第一行两个正整数 $n,q$。接下来 $n$ 行，每行两个字符串 $s_{i,1},s_{i,2}$。随后 $q$ 行，每行两个字符串 $t_{j,1},t_{j,2}$。

输出格式

输出 $q$ 行，每行一个非负整数，表示对应询问的替换方案数。

样例 1

输入

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

输出

2
0

样例 2

输入

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

输出

0
0
0
0

数据范围

设 $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\le2\times10^5$，$2\le L_1,L_2\le5\times10^6$；所有字符串仅含小写英文字母，各二元组等长，每个询问的两个字符串不同。

原卷完整题面

以下保留原卷的图示、完整样例解释、分档约束和特殊性质，便于核对。原卷中引用的外部样例文件未随本次题面上传。

下载原卷题面 PDF