这个主要是写给自己看的。
就是观察到 b 性质是个扫描线。
考虑加强，会发现把 trie 树套上去就没了。
前面的思路不难想，主要是最后一步。
代码：
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
#define N 200010
#define L 5000010
const int base=13331,mod=1e9+9;
int n,q,ans[N],tot,idx,prid[N],sfid[N],pid[N],sid[N],ps[N],ss[N],pt[N],st[N];
unsigned int gtid(unsigned int h1,int h2){return h1*1000000000000037ll+h2;}
string s[N][2],t[N][2];
vector<int>gua[N],ask[N];
int lowbit(int x){return x&(-x);}
struct treearray{int c[L],lim;void init(int lm){lim=lm;rep(i,0,lim){c[i]=0;}}void add(int x,int k){for(;x<=lim;x+=lowbit(x)){c[x]+=k;}}int ask(int x){int s=0;for(;x;x-=lowbit(x)){s+=c[x];}return s;}
}tra;
struct trie{int tot,idx,dfn[L],low[L];vector<pair<int,int>>to[L];vector<int>gua[L],gui[L];void clr(){rep(i,0,tot){to[i].clear();gua[i].clear();gui[i].clear();}idx=0;tot=1;}void ins(string s,int id,int op){int x=1;rep(i,0,(int)s.size()-1){int nxt=0;for(pair<int,int>p:to[x]){if(p.second==s[i]){nxt=p.first;break;}}if(!nxt){tot++;to[x].push_back({tot,s[i]});nxt=tot;}x=nxt;}if(op==0){prid[id]=x;gua[x].push_back(id);}if(op==1){sfid[id]=x;gua[x].push_back(id);}if(op==2){pid[id]=x;gui[x].push_back(id);}if(op==3){sid[id]=x;gui[x].push_back(id);}}void init(int x){idx++;dfn[x]=idx;for(pair<int,int>p:to[x]){init(p.first);}low[x]=idx;}
}trpre,trsuf;
void calc(int x){for(int id:trpre.gua[x]){int oth=sfid[id];tra.add(trsuf.dfn[oth],1);tra.add(trsuf.low[oth]+1,-1);}for(int id:trpre.gui[x]){int oth=sid[id];ans[id]=tra.ask(trsuf.dfn[oth]);}for(pair<int,int> p:trpre.to[x]){calc(p.first);}for(int id:trpre.gua[x]){int oth=sfid[id];tra.add(trsuf.dfn[oth],-1);tra.add(trsuf.low[oth]+1,1);}
}
gp_hash_table<unsigned int,int>mp;
signed main(){freopen("replace3.in","r",stdin);freopen("replace.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cin>>n>>q;rep(i,1,n){cin>>s[i][0]>>s[i][1];}rep(i,1,q){cin>>t[i][0]>>t[i][1];}rep(i,1,n){int pre=-1,suf=-1;rep(j,0,s[i][0].size()-1){if(s[i][0][j]!=s[i][1][j]){pre=j;break;}}if(pre==-1){continue;}per(j,s[i][0].size()-1,0){if(s[i][0][j]!=s[i][1][j]){suf=j;break;}}unsigned int hsh1=0;int hsh2=0;rep(j,pre,suf){hsh1=hsh1*base+s[i][0][j];hsh2=(hsh2*base%mod+s[i][0][j])%mod;}rep(j,pre,suf){hsh1=hsh1*base+s[i][1][j];hsh2=(hsh2*base%mod+s[i][1][j])%mod;}if(!mp[gtid(hsh1,hsh2)]){tot++;mp[gtid(hsh1,hsh2)]=tot;}int id=mp[gtid(hsh1,hsh2)];gua[id].push_back(i);ps[i]=pre;ss[i]=suf;}rep(i,1,q){if(t[i][0].size()!=t[i][1].size()){continue;}int pre=-1,suf=-1;rep(j,0,t[i][0].size()-1){if(t[i][0][j]!=t[i][1][j]){pre=j;break;}}per(j,t[i][0].size()-1,0){if(t[i][0][j]!=t[i][1][j]){suf=j;break;}}unsigned int hsh1=0;int hsh2=0;rep(j,pre,suf){hsh1=hsh1*base+t[i][0][j];hsh2=(hsh2*base%mod+t[i][0][j])%mod;}rep(j,pre,suf){hsh1=hsh1*base+t[i][1][j];hsh2=(hsh2*base%mod+t[i][1][j])%mod;}if(!mp[gtid(hsh1,hsh2)]){continue;}int id=mp[gtid(hsh1,hsh2)];ask[id].push_back(i);pt[i]=pre;st[i]=suf;}rep(id,1,tot){if(!ask[id].size()){continue;}trpre.clr();trsuf.clr();for(auto x:gua[id]){string tmp="";per(i,ps[x]-1,0){tmp+=s[x][0][i];}trpre.ins(tmp,x,0);tmp="";rep(i,ss[x]+1,s[x][0].size()-1){tmp+=s[x][0][i];}trsuf.ins(tmp,x,1);}for(auto x:ask[id]){string tmp="";per(i,pt[x]-1,0){tmp+=t[x][0][i];}trpre.ins(tmp,x,2);tmp="";rep(i,st[x]+1,t[x][0].size()-1){tmp+=t[x][0][i];}trsuf.ins(tmp,x,3);}trpre.init(1);trsuf.init(1);tra.init(max(trpre.idx,trsuf.idx));calc(1);}rep(i,1,q){cout<<ans[i]<<'\n';}return 0;
}