如果某个串(b)是(a_j)的前缀,并且(a_i)支配(b),那么(a_i)后面就可以放(a_j),所以如果把对应的图建出来,问题就是求最长链,如果有环就是无限长
说到前缀,我们可以把所有(a)串建一棵(Trie),然后某个(a_i)支配的(b)串节点对应的子树内的(a_j)串节点都可以连边((i,j)).不过每次建(Trie)太慢了,我们可以利用(SAM)建后缀树,然后每次相当于一个点给某个点子树内的点连边,所以后缀树上父亲向儿子连边,然后每次某个点向另一个点连边就好了
注意有可能(a)和(b)在同一个节点,但是(len(a)<len(b)),所以要暴力把这些点插进去,形成新的(Trie)
实现的话,因为子树内的点在dfn序上是区间,所以我用的线段树优化连边(逃,然后最长链可以拓扑排序
// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#define LL long long
#define db double
using namespace std;
const int N=2e5+10;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[N*40],nt[N*40],hd[N<<3],dg[N<<3],tot;
void add(int x,int y){++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot,++dg[y];}
int qto[N<<1],qnt[N<<1],qhd[N<<1],qt;
void qwq(int x,int y){++qt,qto[qt]=y,qnt[qt]=qhd[x],qhd[x]=qt;}
int st[N<<1],ts,ln[N<<1];
char cc[N];
int n,m,tp,lz,n1,n2,dfn[N<<1],ii[N],a[N<<4],pp[N<<1];
LL ans,di[N<<4];
int fa[N<<1][19],ff[N<<1],ch[N<<1][26],sz[N<<1],len[N<<1],tt=1,la=1,ti;
int newnode(){++tt,memset(fa[tt],0,sizeof(fa[tt])),memset(ch[tt],0,sizeof(ch[tt])),len[tt]=0;return tt;}
void clr(){memset(a,0,sizeof(int)*(tp+3)),memset(di,0,sizeof(LL)*(tp+3)),la=1,tt=0,newnode();}
void extd(int x,int i)
{
int np=newnode(),p=la;
len[np]=len[p]+1,ii[i]=np,la=np;
while(p&&!ch[p][x]) ch[p][x]=np,p=fa[p][0];
if(!p) fa[np][0]=1;
else
{
int q=ch[p][x];
if(len[q]==len[p]+1) fa[np][0]=q;
else
{
int nq=newnode();
fa[nq][0]=fa[q][0],len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[np][0]=fa[q][0]=nq;
while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p][0];
}
}
}
void dfs(int x)
{
dfn[x]=++ti,sz[x]=1;
for(int j=1;j<=lz;++j)
{
fa[x][j]=fa[fa[x][j-1]][j-1];
if(!fa[x][j]) break;
}
for(int i=hd[x];i;i=nt[i])
dfs(to[i]),sz[x]+=sz[to[i]];
}
bool cmp(int a,int b){return ln[a]!=ln[b]?ln[a]<ln[b]:a>b;}
void dfs2(int x,int ffa)
{
ts=0;
for(int i=qhd[x];i;i=qnt[i]) st[++ts]=qto[i];
sort(st+1,st+ts+1,cmp);
for(int i=1;i<=ts;++i)
ff[st[i]]=ffa,ffa=st[i];
for(int i=hd[x];i;i=nt[i])
dfs2(to[i],ffa);
}
int ch2[N<<4][2],rt,b[N<<1];
void inii(int o,int l,int r)
{
if(l==r) {pp[l]=o;return;}
int mid=(l+r)>>1;
++tp,ch2[o][0]=tp,add(o,ch2[o][0]);
inii(ch2[o][0],l,mid);
++tp,ch2[o][1]=tp,add(o,ch2[o][1]);
inii(ch2[o][1],mid+1,r);
}
void link(int o,int l,int r,int ll,int rr)
{
if(ll<=l&&r<=rr){add(tp,o);return;}
int mid=(l+r)>>1;
if(ll<=mid) link(ch2[o][0],l,mid,ll,rr);
if(rr>mid) link(ch2[o][1],mid+1,r,ll,rr);
}
int main()
{
//wssd
len[0]=-1;
int T=rd();
while(T--)
{
scanf("%s",cc+1);
n=strlen(cc+1);
lz=log2(n);
clr();
for(int i=n;i;--i) extd(cc[i]-'a',i);
m=tt;
memset(hd,0,sizeof(int)*(m+3)),tot=0;
for(int i=2;i<=m;++i) add(fa[i][0],i);
dfs(1);
n1=rd();
memset(qhd,0,sizeof(int)*(m+3)),qt=0;
for(int i=1;i<=n1;++i)
{
int l=rd(),r=rd();
ln[i+1]=r-l+1;
int x=ii[l];
for(int j=lz;~j;--j)
if(len[fa[x][j]]>=r-l+1) x=fa[x][j];
qwq(x,i+1);
}
n2=rd();
for(int i=1;i<=n2;++i)
{
int l=rd(),r=rd();
ln[i+n1+1]=r-l+1;
int x=ii[l];
for(int j=lz;~j;--j)
if(len[fa[x][j]]>=r-l+1) x=fa[x][j];
qwq(x,i+n1+1);
}
dfs2(1,1);
m=n1+n2+1;
memset(hd,0,sizeof(int)*(m+3)),tot=0;
for(int i=2;i<=m;++i) add(ff[i],i);
memset(sz,0,sizeof(int)*(m+3));
ti=0,dfs(1);
tp=max(tp,max(m,tt));
memset(hd,0,sizeof(int)*(tp+3)),memset(dg,0,sizeof(int)*(tp+3)),tot=0;
tp=0;
++tp,inii(rt=1,1,m);
memset(b,0,sizeof(int)*(m+3));
int qq=rd();
while(qq--)
{
int x=rd()+1,y=rd()+n1+1;
++tp,add(pp[dfn[x]],tp),link(rt,1,m,dfn[y],dfn[y]+sz[y]-1);
++b[dfn[y]],--b[dfn[y]+sz[y]];
}
memset(a,0,sizeof(int)*(tp+3)),memset(di,0,sizeof(int)*(tp+3));
for(int i=1;i<=n1;++i) a[pp[dfn[i+1]]]=ln[i+1];
queue<int> q;
if(!dg[1]) q.push(1);
/*for(int i=1;i<=m;++i)
{
b[i]+=b[i-1];
if(!b[i]) dg[pp[i]]=0,q.push(pp[i]);
}*/
ans=0;
while(!q.empty())
{
int x=q.front();
q.pop();
ans=max(ans,di[x]);
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
--dg[y],di[y]=max(di[y],di[x]+a[y]);
if(!dg[y]) q.push(y);
}
}
for(int i=1;i<=tp;++i)
if(dg[i]&&a[i]) {ans=-1;break;}
printf("%lld
",ans);
}
return 0;
}