好难写的字符串+数据结构问题，写+调了一下午的说

首先理解题意后我们对问题进行转化，对于每个字符串我们用一个点来代表它们，其中\(A\)类串的点权为它们的长度，\(B\)类串的权值为\(0\)

这样我们根据题意把\(A\to B\)的边连起来，同时每个\(B\)类串向所有以其为前缀的\(A\)类串连边

这样我们就得到了一张DAG（如果不是的话就输出\(-1\)），然后对于它拓扑排序之后求权值和最大链即可

但是第二类边该怎么连呢，下面我们来分析一下具体操作

---

SA转化问题

首先关于这种前后缀相关的问题，我们大可以利用SA来搞

先对于原串建出SA，然后对于每一个\(B\)类串\(b_i\)，我们找到\(rk_{lb_{b_i}}\)，然后二分向两边扩展找出与它\(\operatorname{LCP}\ge len_{b_i}\)的最大区间（可利用关于\(\operatorname{LCP}\)的定理证明单调性）

然后我们直接从这个\(B\)类串向找到的区间连边？所以直接一发线段树优化建图就OK了？

但是有一个问题，就是SA上的后缀长度和实际长度不相等，所以可能会出现\(|A<|B|\)的情况，此时显然\(B\)不能算作\(A\)的前缀

所以我们要请出一个全新的技巧——主席树优化建图

---

主席树优化建图

由于这里最难处理的还是字符串长度，所以我们以此为版本建立主席树

\(A\)类串的处理比较简单，我们可以直接从它对应版本对应\(rk\)的点向它连边

然后对于\(B\)类串，向对应版本的区间连边，同时为了使复杂度不爆炸我们从父节点向子节点连边，这样区间连边的复杂度就是\(\log n\)级别的

然后对于主席树之间，我们从小到大连边，这样就保证了只能向长度更大的串走

所以这道题顺利完成了

---

复杂度分析

首先由于这题中的各种东西都可以认为与\(N\)同阶，那么：

总点数：\(n+n\log n\)；总边数：\(2n+4n\log n\)；总复杂度：\(O(T\cdot n\log n)\)

CODE

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstring>

#include<iostream>

#define RI register int

#define CI const int&

#define Tp template <typename T>

#define Ms(f,x) memset(f,x,sizeof(f))

using namespace std;

typedef long long LL;

const int N=2e5+5,P=20,AN=(N<<1)+N*P,AM=(N<<1)+(N*P<<2);

struct edge

{

    int to,nxt;

}e[AM]; int head[AN],cnt,tot,x,y; vector <int> v[N];

char s[N]; int t,m,len,na,nb,la[N],ra[N],lb[N],rb[N];

int deg[AN],rt[N],rt_[N],q[AN],val[AN]; long long f[AN];

inline void add(CI x,CI y)

{

    if (!y) return; e[++cnt]=(edge){y,head[x]}; head[x]=cnt; ++deg[y];

}

class President_Tree

{

    private:

        int ch[AN][2],cur;

        inline int insert(CI lst,int &now,CI pos,CI l=1,CI r=len)

        {

            now=++tot; ch[tot][0]=ch[lst][0]; ch[tot][1]=ch[lst][1];

            add(now,lst); if (l==r) return now; int mid=l+r>>1,id;

            if (pos<=mid) id=insert(ch[lst][0],ch[now][0],pos,l,mid);

            else id=insert(ch[lst][1],ch[now][1],pos,mid+1,r);

            add(now,ch[now][0]); add(now,ch[now][1]); return id;

        }

    public:

        inline void clear(void)

        {

            for (RI i=1;i<=tot;++i) ch[i][0]=ch[i][1]=0; tot=cur=0;

        }

        inline int insert(CI len,CI pos)

        {

            ++cur; int id=insert(rt_[cur-1],rt_[cur],pos); rt[len]=rt_[cur]; return id;

        }

        #define O num,beg,end

        inline void link(CI now,CI num,CI beg,CI end,CI l=1,CI r=len)

        {

            if (!now) return; if (beg<=l&&r<=end) return add(num,now); int mid=l+r>>1;

            if (beg<=mid) link(ch[now][0],O,l,mid); if (end>mid) link(ch[now][1],O,mid+1,r);

        }

        #undef O

}SEG;

class Suffix_Array

{

    private:

        int sa[N],t[N],bkt[N],hgt[N],log[N],f[N][P],size;

        inline void Radix_Sort(CI n)

        {

            RI i; for (i=0;i<=size;++i) bkt[i]=0;

            for (i=1;i<=n;++i) ++bkt[rk[i]];

            for (i=1;i<=size;++i) bkt[i]+=bkt[i-1];

            for (i=n;i;--i) sa[bkt[rk[t[i]]]--]=t[i];

        }

        inline void build(char *s,CI n)

        {

            RI i; for (size=122,i=1;i<=n;++i) rk[i]=s[i],t[i]=i;

            Radix_Sort(n); for (RI w=1,p=1;p<n;size=p,w<<=1)

            {

                for (p=0,i=n-w+1;i<=n;++i) t[++p]=i;

                for (i=1;i<=n;++i) if (sa[i]>w) t[++p]=sa[i]-w;

                Radix_Sort(n); swap(rk,t); rk[sa[1]]=p=1;

                for (i=2;i<=n;++i) rk[sa[i]]=(t[sa[i-1]]==t[sa[i]]&&t[sa[i-1]+w]==t[sa[i]+w])?p:++p;

            }

        }

        inline void get_height(char *s,CI n)

        {

            RI i,lst=0; for (i=1;i<=n;++i) rk[sa[i]]=i;

            for (i=1;i<=n;++i)

            {

                if (rk[i]==1) continue; if (lst) --lst; int pos=sa[rk[i]-1];

                while (pos+lst<=n&&i+lst<=n&&s[pos+lst]==s[i+lst]) ++lst; hgt[rk[i]]=lst;

            }

        }

        inline int min(CI a,CI b)

        {

            return a<b?a:b;

        }

        inline int LCP(int x,int y)

        {

            if (x>y) swap(x,y); ++x; int k=log[y-x+1];

            return min(f[x][k],f[y-(1<<k)+1][k]);

        }

    public:

        int rk[N];

        inline void init(char *s,CI n)

        {

            RI i; build(s,n); get_height(s,n);

            for (log[0]=-1,i=1;i<=n;++i) log[i]=log[i>>1]+1;

            for (i=1;i<=n;++i) f[i][0]=hgt[i];

            for (RI j=1;j<P;++j) for (i=1;i+(1<<j)-1<=n;++i)

            f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);

        }

        inline void work(CI id)

        {

            int pos=rk[lb[id]],l,r,mid,nl=rb[id]-lb[id]+1,ret1=pos,ret2=pos;

            l=1; r=pos-1; while (l<=r) if (LCP(mid=l+r>>1,pos)>=nl) ret1=mid,r=mid-1; else l=mid+1;

            l=pos+1; r=len; while (l<=r) if (LCP(mid=l+r>>1,pos)>=nl) ret2=mid,l=mid+1; else r=mid-1;

            SEG.link(rt[nl],na+id,ret1,ret2);

        }

}SA;

inline void maxer(LL& x,const LL& y)

{

    if (y>x) x=y;

}

#define to e[i].to

inline LL Topo_Sort(LL ans=0)

{

    RI H=0,T=0,i; for (i=1;i<=na;++i) f[i]=val[i]=ra[i]-la[i]+1;

    for (i=1;i<=tot;++i) if (!deg[i]) q[++T]=i; while (H<T)

    {

        int now=q[++H]; for (maxer(ans,f[now]),i=head[now];i;i=e[i].nxt)

        if (maxer(f[to],f[now]+val[to]),!--deg[to]) q[++T]=to;

    }

    return T!=tot?-1:ans;

}

#undef to

inline void solve(void)

{

    RI i; scanf("%s",s+1); len=strlen(s+1); SA.init(s,len);

    for (scanf("%d",&na),i=1;i<=na;++i)

    scanf("%d%d",&la[i],&ra[i]),v[ra[i]-la[i]+1].push_back(i);

    for (scanf("%d",&nb),i=1;i<=nb;++i) scanf("%d%d",&lb[i],&rb[i]);

    for (tot=na+nb,i=len;i;--i)

    {

        rt[i]=rt[i+1]; for (int it:v[i])

        add(SEG.insert(i,SA.rk[la[it]]),it);

    }

    for (i=1;i<=nb;++i) SA.work(i); for (scanf("%d",&m),i=1;i<=m;++i)

    scanf("%d%d",&x,&y),add(x,na+y); printf("%lld\n",Topo_Sort());

}

inline void clear(void)

{

    cnt=0; Ms(head,0); Ms(deg,0); SEG.clear(); Ms(f,0); Ms(val,0);

    for (RI i=1;i<=len;++i) rt[i]=rt_[i]=0,v[i].clear();

}

int main()

{

    //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);

    for (scanf("%d",&t);t;--t) solve(),clear(); return 0;

}