[十二省联考 2019] 字符串问题

Yazid 和 Tiffany 喜欢字符串问题。在这里，我们将给你介绍一些关于字符串的基本概念。 对于一个字符串 $S$ ，我们定义 $|S|$ 表示 $S$ 的长度。 接着，我们定义该串的子串 $S(L, R)$ 表示由 $S$ 中从左往右数，第 $L$ 个字符到第 $R$ 个字符依次连接形成的字符串，特别地，如果 $L < 1$ 或 $R > |S|$ 或 $L > R$，则 $S(L, R)$ 表示空串。 我们说两个字符串相等，当且仅当它们的长度相等，且从左至右各位上的字符依次 相同。 我们说一个字符串 $T$ 是 $S$ 的前缀，当且仅当 $S(1, |T|) = T$。 两个字符串 $S$, $T$ 相加 $S + T$ 表示的是在 $S$ 后紧挨着写下 $T$ 得到的长度为 $|S| + |T|$ 的字符串。

现有一个字符串 $S$。 Tiffany 将从中划出 $n_a$ 个子串作为 $A$ 类串，第 $i$ 个（$1 \leqslant i \leqslant n_a$）为 $A_i = S(la_i, ra_i)$。 类似地，Yazid 将划出 $n_b$ 个子串作为 $B$ 类串，第 $i$ 个（$1 \leqslant i \leqslant n_b$）为 $B_i = S(lb_i, rb_i)$。 现额外给定 $m$ 组支配关系，每组支配关系 $(x, y)$ 描述了第 $x$ 个 $A$ 类串**支配** 第 $y$ 个 $B$ 类串。 求一个**长度最大**的目标串 $T$，使得存在一个串 $T$ 的分割 $T = t_1+t_2+· · ·+t_k$（$k \geqslant 0$）满足： - 分割中的每个串 $t_i$ 均为 $A$ 类串：即存在一个与其相等的 $A$ 类串，不妨假设其为 $t_i = A_{id_i}$。 - 对于分割中所有相邻的串 $t_i, t_{i+1}$（$1 \leqslant i < k$），都有存在一个$A_{id_i}$ 支配的 $B$ 类串，使得该 $B$ 类串为 $t_{i+1}$ 的前缀。 方便起见，你只需要输出这个最大的长度即可。 特别地，如果存在无限长的目标串（即对于任意一个正整数 $n$，都存在一个满足限制的长度超过 $n$ 的串），请输出 $-1$。

单个测试点中包含多组数据，输入的第一行包含一个非负整数 $T$ 表示数据组数。接下来依次描述每组数据，对于每组数据： - 第 $1$ 行一个只包含小写字母的字符串 $S$。 - 第 $2$ 行一个非负整数 $n_a$，表示 $A$ 类串的数目。接下来 $n_a$ 行，每行 $2$ 个用空格隔开的整数。 - 这部分中第 $i$ 行的两个数分别为 $la_i$, $ra_i$，描述第 $i$ 个 $A$ 类串。 - 保证 $1 \leqslant la_i \leqslant ra_i \leqslant |S|$。 - 接下来一行一个非负整数 $n_b$，表示 $B$ 类串的数目。接下来 $n_b$ 行，每行 $2$ 个用空格隔开的整数。 - 这部分中第 $i$ 行的两个数分别为 $lb_i$, $rb_i$，描述第 $i$ 个 $B$ 类串。 - 保证 $1 \leqslant lb_i \leqslant rb_i \leqslant |S|$。 - 接下来一行一个非负整数 $m$，表示支配关系的组数。接下来 $m$ 行，每行 $2$ 个用空格隔开的整数。 - 这部分中每行的两个整数 $x$, $y$，描述一对 $(x, y)$ 的支配关系，具体意义见 【题目描述】。 - 保证 $1 \leqslant x \leqslant n_a$，$1 \leqslant y \leqslant n_b$。保证所有支配关系两两不同，即不存在两组支配关系的 $x, $y **均**相同。

依次输出每组数据的答案，对于每组数据： - 一行一个整数表示最大串长。特别地，如果满足限制的串可以是无限长的，则请 输出 $-1$。

3
abaaaba
2
4 7
1 3
1
3 4
1
2 1
abaaaba
2
4 7
1 3
1
7 7
1
2 1
abbaabbaab
4
1 5
4 7
6 9
8 10
3
1 6
10 10
4 6
5
1 2
1 3
2 1
3 3
4 1

7
-1
13

#### 样例一解释 对于第 $1$ 组数据，$A$ 类串有 $\texttt{aaba}$ 与 $\texttt{aba}$，$B$ 类串有 $\texttt{aa}$，且 $A_2$ 支配 $B_1$。我们可以找到串 $\texttt{abaaaba}$，它可以拆分成 $A_2 + A_1$，且 $A_1$ 包含由 $A_2$ 所支配的 $B_1$ 作为前缀。可以证明不存在长度更大的满足限制的串。 对于第 $2$ 组数据，与第 $1$ 组数据唯一不同的是，唯一的 $B$ 类串为 $\texttt{a}$。容易证明存在无限长的满足限制的串。 对于第 $3$ 组数据，容易证明 $\texttt{abbaabbaaaabb}$ 是最长的满足限制的串。 #### 子任务  为了方便你的阅读，我们把**测试点编号**放在了表格的中间，请你注意这一点。 表格中的 $|A_i| > |B_j|$ 指的是**任意** $B$ 类串的长度不超过**任意** $A$ 类串的长度。 对于所有测试点，保证：$T \leqslant 100$，且对于测试点内所有数据，$|S|$, $n_a$, $n_b$, $m$ 的**总和**分别不会超过**该测试点中对应**的**单组数据的限制**的 $10$ 倍。比如，对于第 $1$ 组测试点，就有 $\sum n_a \leqslant 10 \times 100 = 1000$ 等。特别地，我们规定对于测试点 $4$，有 $T \leqslant 10$。 对于所有测试点中的每一组数据，保证：$1 \leqslant |S| \leqslant 2 \times 10^5$，$n_a$, $n_b \leqslant 2 \times 10^5$，$m \leqslant 2 \times 10^5$ #### 提示 十二省联考命题组温馨提醒您： **数据千万条，清空第一条。** **多测不清空，爆零两行泪。**