P5284 [12 Provinces Joint Exam 2019] String Problem

Yazid and Tiffany like string problems. Here, we will introduce some basic concepts about strings. For a string $S$, we define $|S|$ as the length of $S$. Next, we define the substring $S(L, R)$ as the string formed by concatenating, in order from left to right, the $L$-th character through the $R$-th character of $S$. In particular, if $L < 1$ or $R > |S|$ or $L > R$, then $S(L, R)$ denotes the empty string. We say two strings are equal if and only if they have the same length, and their characters are identical at every position from left to right. We say a string $T$ is a prefix of $S$ if and only if $S(1, |T|) = T$. For two strings $S$ and $T$, their concatenation $S + T$ means writing $T$ immediately after $S$, producing a string of length $|S| + |T|$.

You are given a string $S$. Tiffany will select $n_a$ substrings as type $A$ strings. The $i$-th one ($1 \leqslant i \leqslant n_a$) is $A_i = S(la_i, ra_i)$. Similarly, Yazid will select $n_b$ substrings as type $B$ strings. The $i$-th one ($1 \leqslant i \leqslant n_b$) is $B_i = S(lb_i, rb_i)$. Additionally, you are given $m$ dominance relations. Each relation $(x, y)$ states that the $x$-th type $A$ string **dominates** the $y$-th type $B$ string. Find a target string $T$ with the **maximum possible length**, such that there exists a partition of $T$ as $T = t_1+t_2+· · ·+t_k$ ($k \geqslant 0$) satisfying: - Every string $t_i$ in the partition is a type $A$ string: that is, there exists a type $A$ string equal to it. WLOG, assume $t_i = A_{id_i}$. - For every pair of adjacent strings $t_i, t_{i+1}$ ($1 \leqslant i < k$), there exists a type $B$ string dominated by $A_{id_i}$, such that this type $B$ string is a prefix of $t_{i+1}$. For convenience, you only need to output this maximum length. In particular, if there exists an infinitely long target string (that is, for any positive integer $n$, there exists a string satisfying the constraints whose length is greater than $n$), output $-1$.

Each test file contains multiple datasets. The first line contains a non-negative integer $T$ indicating the number of datasets. Then each dataset is described as follows: - Line $1$: a string $S$ consisting only of lowercase letters. - Line $2$: a non-negative integer $n_a$, the number of type $A$ strings. The next $n_a$ lines each contain two integers separated by a space. - In this part, the two integers on line $i$ are $la_i$, $ra_i$, describing the $i$-th type $A$ string. - It is guaranteed that $1 \leqslant la_i \leqslant ra_i \leqslant |S|$. - Next line: a non-negative integer $n_b$, the number of type $B$ strings. The next $n_b$ lines each contain two integers separated by a space. - In this part, the two integers on line $i$ are $lb_i$, $rb_i$, describing the $i$-th type $B$ string. - It is guaranteed that $1 \leqslant lb_i \leqslant rb_i \leqslant |S|$. - Next line: a non-negative integer $m$, the number of dominance relations. The next $m$ lines each contain two integers separated by a space. - The two integers $x$, $y$ on each line describe a dominance relation $(x, y)$; see 【Description】 for details. - It is guaranteed that $1 \leqslant x \leqslant n_a$, $1 \leqslant y \leqslant n_b$. All dominance relations are pairwise distinct, i.e., there do not exist two relations with both the same $x$ and the same $y$.

Output the answer for each dataset in order. For each dataset: - Output one integer per line, the maximum length of such a string. In particular, if a string satisfying the constraints can be infinitely long, output $-1$.

#### Explanation of Sample 1 For dataset $1$, the type $A$ strings are $\texttt{aaba}$ and $\texttt{aba}$, the type $B$ string is $\texttt{aa}$, and $A_2$ dominates $B_1$. We can find the string $\texttt{abaaaba}$, which can be split into $A_2 + A_1$, and $A_1$ has $B_1$ (dominated by $A_2$) as a prefix. It can be proven that no longer string satisfying the constraints exists. For dataset $2$, the only difference from dataset $1$ is that the only type $B$ string is $\texttt{a}$. It is easy to prove that an infinitely long string satisfying the constraints exists. For dataset $3$, it is easy to prove that $\texttt{abbaabbaaaabb}$ is the longest string satisfying the constraints. #### Subtasks |$n_a$|$n_b$|$\lvert S\rvert$|Test Point|$m$|$\lvert A_i\rvert \geq \lvert B_j\rvert$|Other Constraints| |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$\leq 100$|$\leq 100$|$\leq 10^4$|$1$|$\leq 10^4$|Guaranteed|Guaranteed that all $\lvert A_i\rvert,\lvert B_j\rvert\leq 100$| |$\leq 1000$|$\leq 1000$|$\leq 2\times 10^5$|$2\sim 3$|$\leq 2\times 10^5$|Guaranteed|None| |$=1$|$\leq 2\times 10^5$|$\leq 2\times 10^5$|$4$|$=n_b$|Guaranteed|None| |$\leq 2\times 10^5$|$\leq 2\times 10^5$|$\leq 2\times 10^5$|$5\sim 6$|$\leq 2\times 10^5$|Guaranteed|Guaranteed that all $ra_i +1=la_{i+1}$| |$\leq 2\times 10^5$|$\leq 2\times 10^5$|$\leq 2\times 10^5$|$7\sim 8$|$\leq 2\times 10^5$|Guaranteed|None| |$\leq 2\times 10^5$|$\leq 2\times 10^5$|$\leq 2\times 10^5$|$9\sim 10$|$\leq 2\times 10^5$|Not guaranteed|None| For easier reading, the **test point numbers** are placed in the middle of the table. Please pay attention to this. In the table, $|A_i| > |B_j|$ means that the length of **any** type $B$ string does not exceed the length of **any** type $A$ string. For all test points, it is guaranteed that $T \leqslant 100$, and within each test point, across all datasets, the **totals** of $|S|$, $n_a$, $n_b$, and $m$ will each not exceed $10$ times the per-dataset limit for that test point. For example, for test point $1$, we have $\sum n_a \leqslant 10 \times 100 = 1000$, etc. In particular, for test point $4$, we require $T \leqslant 10$. For every dataset in all test points, it is guaranteed that: $1 \leqslant |S| \leqslant 2 \times 10^5$, $n_a, n_b \leqslant 2 \times 10^5$, $m \leqslant 2 \times 10^5$. #### Hint A friendly reminder from the 12 Provinces Joint Exam problem setters: **There are thousands of testdata, clear the first one.** **If you do not clear between multiple tests, you will get zero points and shed two lines of tears.** Translated by ChatGPT 5