CF1714D.Color with Occurrences

You are given some text $t$ and a set of $n$ strings $s_1, s_2, \dots, s_n$.

In one step, you can choose any occurrence of any string $s_i$ in the text $t$ and color the corresponding characters of the text in red. For example, if $t=\texttt{bababa}$ and $s_1=\texttt{ba}$, $s_2=\texttt{aba}$, you can get $t=\color{red}{\texttt{ba}}\texttt{baba}$, $t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$ or $t=\texttt{bab}\color{red}{\texttt{aba}}$ in one step.

You want to color all the letters of the text $t$ in red. When you color a letter in red again, it stays red.

In the example above, three steps are enough:

• Let's color $t[2 \dots 4]=s_2=\texttt{aba}$ in red, we get $t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$;
• Let's color $t[1 \dots 2]=s_1=\texttt{ba}$ in red, we get $t=\color{red}{\texttt{baba}}\texttt{ba}$;
• Let's color $t[4 \dots 6]=s_2=\texttt{aba}$ in red, we get $t=\color{red}{\texttt{bababa}}$.

Each string $s_i$ can be applied any number of times (or not at all). Occurrences for coloring can intersect arbitrarily.

Determine the minimum number of steps needed to color all letters $t$ in red and how to do it. If it is impossible to color all letters of the text $t$ in red, output -1.

给你一段文本 $t$ 和一个包含 $n$ 个字符串的集合 $s_1, s_2, \dots, s_n$。

每一步中，你可以选择文本 $t$ 中任意一个字符串 $s_i$ 的任意一次出现，并将该出现所对应位置的字符染成红色。例如，若 $t=\texttt{bababa}$，且 $s_1=\texttt{ba}$、$s_2=\texttt{aba}$，则一步操作后可得到 $t=\color{red}{\texttt{ba}}\texttt{baba}$、$t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$ 或 $t=\texttt{bab}\color{red}{\texttt{aba}}$。

你的目标是将文本 $t$ 中的所有字母都染成红色。若某个字母已被染红，再次对其染色不会改变其颜色（即仍为红色）。

在上述例子中，三步操作即可完成全部染色：

• 将 $t[2 \dots 4]=s_2=\texttt{aba}$ 染红，得到 $t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$；
• 将 $t[1 \dots 2]=s_1=\texttt{ba}$ 染红，得到 $t=\color{red}{\texttt{baba}}\texttt{ba}$；
• 将 $t[4 \dots 6]=s_2=\texttt{aba}$ 染红，得到 $t=\color{red}{\texttt{bababa}}$。

每个字符串 $s_i$ 可以被使用任意多次（也可以完全不使用）。用于染色的字符串出现位置可以任意重叠。

请确定将文本 $t$ 中所有字母染成红色所需的最少步数，以及一种具体的染色方案。如果无法将文本 $t$ 中所有字母都染成红色，请输出 -1。

The first line of the input contains an integer $q$ ($1 \le q \le 100$) —the number of test cases in the test.

The descriptions of the test cases follow.

The first line of each test case contains the text $t$ ($1 \le |t| \le 100$), consisting only of lowercase Latin letters, where $|t|$ is the length of the text $t$.

The second line of each test case contains a single integer $n$ ($1 \le n \le 10$) — the number of strings in the set.

This is followed by $n$ lines, each containing a string $s_i$ ($1 \le |s_i| \le 10$) consisting only of lowercase Latin letters, where $|s_i|$ — the length of string $s_i$.

输入的第一行包含一个整数 $q$（$1 \le q \le 100$），表示测试用例的数量。

随后是各测试用例的描述。

每个测试用例的第一行包含文本 $t$（$1 \le |t| \le 100$），该文本仅由小写拉丁字母组成，其中 $|t|$ 表示文本 $t$ 的长度。

每个测试用例的第二行包含一个整数 $n$（$1 \le n \le 10$），表示集合中字符串的数量。

接下来是 $n$ 行，每行包含一个字符串 $s_i$（$1 \le |s_i| \le 10$），该字符串仅由小写拉丁字母组成，其中 $|s_i|$ 表示字符串 $s_i$ 的长度。

For each test case, print the answer on a separate line.

If it is impossible to color all the letters of the text in red, print a single line containing the number -1.

Otherwise, on the first line, print the number $m$ — the minimum number of steps it will take to turn all the letters $t$ red.

Then in the next $m$ lines print pairs of indices: $w_j$ and $p_j$ ($1 \le j \le m$), which denote that the string with index $w_j$ was used as a substring to cover the occurrences starting in the text $t$ from position $p_j$. The pairs can be output in any order.

If there are several answers, output any of them.

对于每个测试用例，请在单独的一行上输出答案。

如果无法将文本中所有字母染成红色，则输出仅包含数字 $-1$ 的一行。

否则，在第一行输出数字 $m$ —— 即将文本 $t$ 中所有字母变为红色所需的最少步数。

随后的 $m$ 行中，每行输出一对下标：$w_j$ 和 $p_j$（$1 \le j \le m$），表示使用了下标为 $w_j$ 的字符串作为子串，来覆盖文本 $t$ 中从位置 $p_j$ 开始的匹配。这些对可以以任意顺序输出。

若存在多个正确答案，输出其中任意一个即可。

The first test case is explained in the problem statement.

In the second test case, it is impossible to color all the letters of the text in red.

第一个测试用例在题目描述中已作解释。

在第二个测试用例中，无法将文本中的所有字母都染成红色。