← 返回题目列表

Codeforces · 1714/D

D. 颜色与出现次数

中文机器翻译题面 查看原题

给你一些文本 $$$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。

输入

输入的第一行包含一个整数 $$$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$$$ — 将所有字母 $$$t$$$ 变成红色所需的最少步骤数。

然后在接下来的 $$$m$$$ 行中打印索引对:$$$w_j$$$ 和 $$$p_j$$$ ($$$1 \le j \le m$$$),这表示索引为 $$$w_j$$$ 的字符串被用作子字符串来覆盖从位置 $$$p_j$$$ 开始的文本 $$$t$$$ 中出现的情况。这些对可以按任何顺序输出。

如果有多个答案,则输出其中任何一个。

示例

输入 #1

6
bababa
2
ba
aba
caba
2
bac
acab
abacabaca
3
aba
bac
aca
baca
3
a
c
b
codeforces
4
def
code
efo
forces
aaaabbbbcccceeee
4
eeee
cccc
aaaa
bbbb

输出 #1

3
2 2
1 1
2 4
-1
4
1 1
2 6
3 3
3 7
4
3 1
1 2
2 3
1 4
2
4 5
2 1
4
3 1
4 5
2 9
1 13

注意

第一个测试用例在问题陈述中进行了解释。

在第二个测试用例中,不可能将文本的所有字母都涂成红色。