```cpp
namespace tar {
int dfn[N << 3], low[N << 3], cnt, stk[N << 3], top, coc;
bool ins[N << 3], vis[N << 3];
ll ans[N << 3];
inline void init() {
coc = cnt = 0;
for (int i = 1; i <= tot; i++) dfn[i] = low[i] = ans[i] = vis[i] = 0;
}
inline void tarjan(int v) {
low[v] = dfn[v] = ++cnt;
stk[++top] = v, ins[v] = true;
for (edge *i = g.pt[v]; i; i = i->nxt) {
if (!dfn[i->to]) {
tarjan(i->to);
low[v] = min(low[v], low[i->to]);
} else if (ins[i->to])
low[v] = min(low[v], dfn[i->to]);
}
if (low[v] == dfn[v])
for (++coc; stk[top + 1] != v; --top) ins[stk[top]] = false;
}
inline ll dfs(int v) {
if (vis[v])
return ans[v];
vis[v] = true, ans[v] = 0;
for (edge *i = g.pt[v]; i; i = i->nxt) ans[v] = max(ans[v], dfs(i->to));
ans[v] += val[v];
return ans[v];
}
inline ll solve() {
for (int i = 1; i <= tot; i++)
if (!dfn[i])
tarjan(i);
if (coc < tot)
return -1;
ll ret = 0;
for (int i = 1; i <= tot; i++) ret = max(ret, dfs(i));
return ret;
}
}
struct SAM {
struct node {int f, l, trs[26];} t[N << 1];
struct str {
int len, id;
bool operator<(const str &b) const { return len < b.len || (len == b.len && id > b.id); }
};
vector<str> q[N << 1];
int cnt, root, f[N << 1][20];
gra tr;
inline int newnode() {
++cnt,t[cnt].f = t[cnt].l = 0;
for (int i = 0; i < 26; i++) t[cnt].trs[i] = 0;
return cnt;
}
inline void init() {
tr.init(cnt);
for (int i = 1; i <= cnt; i++) q[i].clear();
cnt = 0, root = newnode();
}
inline int insert(int u, int c) {
int x = newnode(), v, w;
t[x].l = t[u].l + 1;
for (; u && !t[u].trs[c]; u = t[u].f) t[u].trs[c] = x;
if (!u) t[x].f = root;
else if (t[v = t[u].trs[c]].l == t[u].l + 1) t[x].f = v;
else {
t[w = ++cnt] = t[v], t[w].l = t[u].l + 1, t[x].f = t[v].f = w;
for (; u && t[u].trs[c] == v; u = t[u].f) t[u].trs[c] = w;
}
return x;
}
inline void build(void) {
for (int i = 1; i <= cnt; i++) f[i][0] = t[i].f;
for (int i = 1; i < 20; i++) for (int j = 1; j <= cnt; j++) f[j][i] = f[f[j][i - 1]][i - 1];
}
inline void addpoint(int v, int len, int id) {
for (int i = 19; i >= 0; i--) if (t[f[v][i]].l >= len) v = f[v][i];
q[v].push_back((str){ len, id });
}
inline int dfs(int v) {
int ret, tl;
if (q[v].size()) {
sort(q[v].begin(), q[v].end()),ret = q[v][0].id, tl = q[v][0].id;
for (unsigned i = 1; i < q[v].size(); i++) g.addedge(q[v][i - 1].id, tl = q[v][i].id);
} else ret = tl = ++tot;
for (edge *i = tr.pt[v]; i; i = i->nxt) g.addedge(tl, dfs(i->to));
return ret;
}
inline void link() {
for (int i = 2; i <= cnt; i++) tr.addedge(t[i].f, i);
dfs(root);
}
} sam;
char s[N];
int pt[N], a[N], b[N], t;
int main() {
// freopen("debug.in","r",stdin);
// freopen("debug.out","w",stdout);
io>>t;
for (t; t >= 1; t--) {
io>>s;
sam.init(), g.init(tot);
for (int i = 1; i <= tot; i++) val[i] = 0;
tar::init(),tot = 0;
int len = strlen(s);
for (int i = len - 1, j = 1; i >= 0; i--) pt[i] = j = sam.insert(j, s[i] - 'a');
sam.build();
int na;io>>na;
for (int i = 1; i <= na; i++) {
int l, r;io>>l>>r;
a[i] = ++tot, ++tot, g.addedge(tot, a[i]),val[a[i]] = r - l + 1,sam.addpoint(pt[l - 1], r - l + 1, tot);
}
int nb;io>>nb;
for (int i = 1; i <= nb; i++) {
int l, r;io>>l>>r;
b[i] = ++tot,sam.addpoint(pt[l - 1], r - l + 1, tot);
}
sam.link();
int m;io>>m;
for (int i = 1; i <= m; i++) {
int x, y;io>>x>>y;
g.addedge(a[x], b[y]);
}
io<<tar::solve()<<endl;
}
return 0;
}
```
by rEdWhitE_uMbrElla @ 2019-04-14 12:19:50
~~切黑题的萌新~~
by Achtoria @ 2019-04-14 12:28:52
~~您不是退役了嘛~~
by 紬文德斯 @ 2019-04-14 13:19:26
orz 您又切大火题
by NaCly_Fish @ 2019-04-14 13:24:09
@[NaCly_Fish](/space/show?uid=115864) orz 您嘲讽他只会切红题（
by SSerxhs @ 2019-04-14 13:38:22
@[SSerxhs](/space/show?uid=29826) 铯的烟色是紫色
by NaCly_Fish @ 2019-04-14 13:40:58
@[NaCly_Fish](/space/show?uid=115864) *焰色
by NaCly_Fish @ 2019-04-14 13:41:48