A5844 · 「十二省联考 2019」字符串问题

题目描述

现有一个字符串 $S$。 Tiffany 将从中划出 $n_a$ 个子串作为 A 类串，第 $i$ 个（$1\leq i\leq n_a$）为 $A_i = S\left( la_i, ra_i\right)$。 类似地，Yazid 将划出 $n_b$ 个子串作为 B 类串，第 $i$ 个（$1\leq i\leq n_b$）为 $B_i = S\left( lb_i, rb_i\right)$。 现额外给定 $m$ 组支配关系，每组支配关系 $\left( x,y\right)$ 描述了第 $x$ 个 A 类串**支配**第 $y$ 个 B 类串。 求一个**长度最大**的目标串 $T$，使得存在一个串 $T$ 的分割 $T=t_1 + t_2 +\dots +t_k$（$k\geq 0$）满足： - 分割中的每个串 $t_i$ 均为 A 类串：即存在一个与其相等的 A 类串，不妨假设其为 $t_i = A_{id_i}$。 - 对于分割中所有相邻的串 $t_i , t_{i+1}$（$1\leq 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\leq la_i\leq ra_i\leq \lvert S\rvert$。 - 接下来一行一个非负整数 $n_b$，表示 B 类串的数目。接下来 $n_b$ 行，每行 $2$ 个用空格隔开的整数。 - 这部分中第 $i$ 行的两个数分别为 $lb_i,rb_i$，描述第 $i$ 个 B 类串。 - 保证 $1\leq lb_i\leq rb_i\leq \lvert S\rvert$。 - 接下来一行一个非负整数 $m$，表示支配关系的组数。接下来 $m$ 行，每行 $2$ 个用空格隔开的整数。 - 这部分中每行的两个整数 $x,y$，描述一对 $\left( x,y\right)$ 的支配关系，具体意义见「题目描述」。 - 保证 $1\leq x\leq n_a$，$1\leq y\leq n_b$。保证所有支配关系两两不同，即不存在两组支配关系的 $x,y$ **均**相同。

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

输入 #1

输出 #1

7
-1
13