GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Monday 1 August 2022

[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 and a set of n strings s1,s2,,sn.

In one step, you can choose any occurrence of any string si in the text t and color the corresponding characters of the text in red. For example, if t=bababa and s1=bas2=aba, you can get t=bababat=bababa or t=bababa 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[24]=s2=aba in red, we get t=bababa;
  • Let's color t[12]=s1=ba in red, we get t=bababa;
  • Let's color t[46]=s2=aba in red, we get t=bababa.

Each string si 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 in red and how to do it. If it is impossible to color all letters of the text t in red, output -1.

Input

The first line of the input contains an integer q (1q100) —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|t|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 (1n10) — the number of strings in the set.

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

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 — 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: wj and pj (1jm), which denote that the line with index wj was used as a substring to cover the occurrences starting in the text t from position pj. The pairs can be output in any order.

If there are several answers, output any of them.

No comments:

Post a Comment