```cpp
#include <iostream>
#include <unordered_map>
#include <string>
#include <queue>
#include <vector>
using namespace std;
using String = basic_string<int>; // 可通过 substr 取子序列
const int kMaxN = 5e6 + 5, kCharSet = 26 * 26;
struct Node {
unordered_map<int, int> ch;
int fail, sum;
};
vector<Node> tr;
int n, q;
string s, t;
void insert(const String &s) {
int p = 0;
for (int i : s) {
if (!tr[p].ch[i]) {
tr.emplace_back();
tr[p].ch[i] = tr.size() - 1;
}
p = tr[p].ch[i];
}
tr[p].sum++;
}
void build() {
queue<int> q;
// 初始化根节点的所有子节点
for (auto &i : tr[0].ch) {
tr[i.second].fail = 0;
q.push(i.second);
}
// BFS 顺序即按层次的拓扑序
vector<int> order;
for (; q.size(); q.pop()) {
int p = q.front();
order.push_back(p);
for (auto &i : tr[p].ch) {
int pty = i.first;
int mmt = i.second;
int f = tr[p].fail;
while (f && !tr[f].ch.count(pty)) {
f = tr[f].fail;
}
if (tr[f].ch.count(pty)) {
tr[mmt].fail = tr[f].ch[pty];
} else {
tr[mmt].fail = 0;
}
q.push(mmt);
}
}
// 按拓扑序把 fail 链上的出现次数累加下来
for (int u : order) {
tr[u].sum += tr[tr[u].fail].sum;
}
}
long long match(const String &s) {
if (s.empty()) {
return 0;
}
int p = 0;
long long res = 0;
for (int c : s) {
while (p && !tr[p].ch.count(c)) {
p = tr[p].fail;
}
auto it = tr[p].ch.find(c);
if (it != tr[p].ch.end()) {
p = it->second;
}
res += tr[p].sum;
}
return res;
}
int calc(char a, char b) {
return (a - 'a') * 26 + (b - 'a');
}
String convert(const string &a, const string &b) {
String res(a.size(), 0);
for (int i = 0; i < (int)a.size(); i++) {
res[i] = calc(a[i], b[i]);
}
return res;
}
String interval(const String &s, int l, int r) {
if (l > r) {
return String();
}
return s.substr(l, r - l + 1);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
tr.reserve(5e6);
tr.emplace_back();
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> s >> t;
String lrh = convert(s, t);
insert(lrh);
}
build();
while (q--) {
cin >> s >> t;
if (s.size() != t.size()) {
cout << "0\n";
continue;
}
String lrh = convert(s, t);
int n = s.size(), wyy = 0, zrr = n - 1;
// [0, wyy) 是最长公共前缀，(zrr, n - 1] 是最长公共后缀
// [wyy, zrr] 是模式串必须覆盖的区域
for (; wyy < n && s[wyy] == t[wyy]; wyy++) { }
for (; zrr >= 0 && s[zrr] == t[zrr]; zrr--) { }
if (wyy > zrr) { // 模式串无须覆盖任何区域，直接输出所有匹配数
cout << match(lrh) << '\n';
} else { // 用容斥求出至少覆盖了 [wyy, zrr] 的匹配数量
cout << match(lrh) - match(interval(lrh, 0, zrr - 1)) - match(interval(lrh, wyy + 1, n - 1)) + match(interval(lrh, wyy + 1, zrr - 1)) << '\n';
}
}
return 0;
}
```