CF1714D Color with Occurrences

给定一个文本 $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$ 的所有字母染成红色所需的最少步数，以及具体的染色方案。如果无法将所有字母染红，输出 $-1$。

输入的第一行包含一个整数 $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$ 的长度。

对于每个测试用例，单独输出一行答案。 如果无法将所有字母染红，输出一行 $-1$。 否则，第一行输出一个整数 $m$，表示将所有字母染红所需的最少步数。 接下来 $m$ 行，每行输出一对整数 $w_j$ 和 $p_j$（$1 \le j \le m$），表示第 $w_j$ 个字符串被用来覆盖从 $t$ 的第 $p_j$ 个位置开始的子串。每对 $(w_j, p_j)$ 的顺序可以任意。 如果有多种方案，输出任意一种即可。

第一个测试用例的详细过程见题目描述。 第二个测试用例中，无法将所有字母染红。 由 ChatGPT 4.1 翻译