[Solution] Color with Occurrences Codeforces Solution

D. Color with Occurrences

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

You want to color all the letters of the text t$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…4]=s2=aba$t[2\dots 4]=s_2=\mathtt{\text{aba}}$ in red, we get t=bababa$t=\mathtt{\text{b}}\mathtt{\text{aba}}\mathtt{\text{ba}}$;
• Let's color t[1…2]=s1=ba$t[1\dots 2]=s_1=\mathtt{\text{ba}}$ in red, we get t=bababa$t=\mathtt{\text{baba}}\mathtt{\text{ba}}$;
• Let's color t[4…6]=s2=aba$t[4\dots 6]=s_2=\mathtt{\text{aba}}$ in red, we get t=bababa$t=\mathtt{\text{bababa}}$.

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied

 arbitrarily.

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

Input

The first line of the input contains an integer q$q$ (1≤q≤100$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$t$ (1≤|t|≤100$1\le |t|\le 100$), consisting only of lowercase Latin letters, where |t|$|t|$ is the length of the text t$t$.

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

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

Output

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$m$ — the minimum number of steps it will take to turn all the letters t$t$ red.

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

If there are several answers, output any of them.