[十二省联考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$。

输入输出样例

输入样例 #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

输出样例 #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}$ 是最长的满足限制的串。 #### 子任务 ![img](https://s2.ax1x.com/2019/04/06/AW276I.png) 为了方便你的阅读,我们把**测试点编号**放在了表格的中间,请你注意这一点。 表格中的 $|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$ #### 提示 十二省联考命题组温馨提醒您: **数据千万条,清空第一条。** **多测不清空,爆零两行泪。**