以此题结束我后缀数组的学习
然而我可能这辈子都结束不了后缀数组了$QAQ$
用$SA$处理出来每个$B$串是那些$A$串的前缀，连边；再把有支配关系的串连边。问题就成了有向图的最长链，拓扑排序顺便判个环，$DP$就完了。
这样边数是$O(n_an_b)$的，能过前$4$个点。
若某个$B$串属于后缀$S(i)$，后缀$S(j)$满足$B$串匹配的条件是$LCP(S(i),S(j))\ge len(B)$，所以在$SA$里可以二分出来每个$B$串能连边的区间，线段树优化建图，边数就能降到$O(n\log n)$。
然后就能拿到$80$分的好成绩。
最后$2$个点中$len(B)$可能大于$len(A)$，而$2$个串连边还有条件为$len(A)\ge len(B)$，以长度造出来主席树，主席树优化建图，边数还是$O(n\log n)$，可以通过此题。
本地$lemon$原数据不吸氧$AC$，然后在洛咕上吸氧拿到了$90$分的好成绩。
于是开始优化常数。。。
通过诸如舍弃$STL$、$fread$、$O_3$等等负优化：
难受，继续去卡常了，代码就咕了$QAQ$
$update$：
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈我刚写完哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈这篇blog哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈就卡过去了哈哈哈哈哈哈哈
（请无视掉上面）
拓扑排序完了之后$DP\rightarrow$ 一边拓扑排序一边$DP$
$40000ms+\rightarrow 32000ms+$
$emm…$
不管了过了就行
咕了的代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 200010
#define inf 0x3f3f3f3f
const int N = maxn << 6;
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
#define ls(x) ls[x]
#define rs(x) rs[x]
/*==============variable==============*/
int cur[N],f[maxn][22],root[maxn],hl[maxn],h[N],ls[N],rs[N],a[maxn][2],b[maxn][2],deg[N],num,numl,len;
int sa[maxn],rk[maxn],tp[maxn],tax[maxn],hei[maxn],lg[maxn],id[maxn],na,nb,n,m,cnt,L,R,poi;
long long g[N];
struct edge{
int pre,to,l;
}e[N<<1];
struct length{
int pre,to;
}le[maxn];
/*==============End==============*/
/*==============Chairman Tree==============*/
inline void add(int from,int to,int l=0){
if(!from||!to)return;
e[++num].pre=h[from],h[from]=num,e[num].to=to,e[num].l=l,++deg[to];
}
inline void add_l(int from,int to){
le[++numl].pre=hl[from],hl[from]=numl,le[numl].to=to;
}
void build(int l,int r,int &node,int ol){
node=++cnt,add(ol,node);
if(l==r){id[poi]=node,g[node]=a[poi][1]-a[poi][0]+1;return;}
int mid=l+r>>1;
if(rk[a[poi][0]]<=mid)rs(node)=rs(ol),build(l,mid,ls(node),ls(ol));
else ls(node)=ls(ol),build(mid+1,r,rs(node),rs(ol));
add(ls(node),node),add(rs(node),node);
}
void modify(int l,int r,int node){
if(!node)return;
if(L<=l&&R>=r){add(node,poi);return;}
int mid=l+r>>1;
if(L<=mid)modify(l,mid,ls(node));
if(R>mid)modify(mid+1,r,rs(node));
}
/*==============End==============*/
/*==============Suffix Array===========*/
void Rsort(){
for(register int i=0;i<=m;++i)tax[i]=0;
for(register int i=1;i<=n;++i)++tax[rk[i]];
for(register int i=1;i<=m;++i)tax[i]+=tax[i-1];
for(register int i=n;i;--i)sa[tax[rk[tp[i]]]--]=tp[i];
}
void Ssort(){
for(register int i=1;i<=n;++i)rk[i]=s[i],tp[i]=i;
m=225,Rsort();
for(register int k=1,p=0;p<n;m=p,k<<=1){
p=0;
for(register int i=1;i<=k;++i)tp[++p]=n-k+i;
for(register int i=1;i<=n;++i)if(sa[i]>k)tp[++p]=sa[i]-k;
Rsort();
for(register int i=1;i<=n;++i)tp[i]=rk[i];
rk[sa[1]]=p=1;
for(register int i=2;i<=n;++i)
rk[sa[i]]=tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k]?p:++p;
}
}
void get_height(){
int k=0,x;
for(register int i=1;i<=n;++i){
if(rk[i]==1)continue;
if(k)--k;
x=sa[rk[i]-1];
while(i+k<=n&&x+k<=n&&s[i+k]==s[x+k])++k;
hei[rk[i]]=f[rk[i]][0]=k;
}
}
void ST(){
for(register int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
for(register int j=1;j<=lg[n];++j)
for(register int i=1;i+(1<<j)-1<=n;++i)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline int query(int l,int r){
if(l>r)return inf;
int len=lg[r-l+1];
return min(f[l][len],f[r-(1<<len)+1][len]);
}
void Prefix_Initialization(){
int l,r,mid,x,len;
for(register int i=1;i<=nb;++i){
x=rk[b[i][0]],len=b[i][1]-b[i][0]+1;
l=1,r=x;
while(l<r){
mid=l+r>>1;
if(query(mid+1,x)>=len)r=mid;
else l=mid+1;
}
L=l,l=x,r=n;
while(l<r){
mid=l+r+1>>1;
if(query(x+1,mid)>=len)l=mid;
else r=mid-1;
}
R=l,poi=i+cnt;
modify(1,n,root[len]);
}
}
/*===============End===============*/
/*===============DP================*/
void topo(){
int node,x,res=0,head=0;
long long ans=0;
for(register int i=1;i<=cnt;++i)if(!deg[i])cur[++len]=i;
while(head<len){
node=cur[++head],ans=max(ans,g[node]);
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to,--deg[x],g[x]=max(g[x],g[node]+e[i].l);
if(!deg[x])cur[++len]=x;
}
}
for(register int i=1;i<=cnt;++i)if(deg[i])ans=-1,deg[i]=0;
printf("%lld\n",ans);
}
/*==================End==================*/
int main(){
int t=read();
while(1){
scanf("%s",s+1),n=strlen(s+1),na=read();
Ssort(),get_height(),ST();
root[n+1]=0;
for(register int i=1;i<=na;++i)a[i][0]=read(),a[i][1]=read(),add_l(a[i][1]-a[i][0]+1,i);
for(register int i=n;i;--i){
int last=root[i+1],node;
for(register int j=hl[i];j;j=le[j].pre)poi=le[j].to,build(1,n,node,last),last=node;
root[i]=last,hl[i]=0;
}
nb=read();
for(register int i=1;i<=nb;++i)b[i][0]=read(),b[i][1]=read();
int m=read(),x,y;
while(m--){
x=read(),y=read();
add(y+cnt,id[x],a[x][1]-a[x][0]+1);
}
Prefix_Initialization();
cnt+=nb;
topo();
if(!--t)break;
for(register int i=1;i<=cnt;++i)h[i]=g[i]=0;
cnt=num=numl=len=0;
memset(tp,0,sizeof tp);
}
}
