Description

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$.

Input Format

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 Format

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$.

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

Hint

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

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