404526: GYM101532 F Strings and Queries

You are given a set of n strings such that all characters in the strings are 'a', 'b', or 'c'.

Also, you are given q queries, such that each query consisting of two strings a and b. The answer of each query is the index of the string with the most number of palindrome substrings between strings a and b from the given set.

A substring of the string s is a sequence s_l, s_l + 1, ..., s_r for some integers (l, r) such that (1 ≤ l ≤ r ≤ n), where n is the length of the string s.

A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as "madam" or "racecar".

The first line contains an integer T, where T is the number of test cases.

The first line of each test case contains two integers n and q (1 ≤ n ≤ 10⁴) (1 ≤ q ≤ 10⁵), where n is the number of strings, and q is the number of queries.

Then n lines follow, each line contains a non-empty string with length no more than 30, giving the strings. All characters in the strings are 'a', 'b', or 'c'. It is guaranteed that all strings are unique. The given strings are numbered from 1 to n.

Then q lines follow, each line contains two strings a and b, giving the queries. It is guaranteed that strings a and b exist in the given set of strings.

For each query, print a single line containing the index of the string with the most number of palindrome substrings between the given strings a and b. If there are more than one answer, print the lowest index.

1
5 5
aaaaa
abaabc
cbbaca
abccba
abca
aaaaa abca
cbbaca abccba
abaabc abccba
abccba abca
abaabc abccba

1
4
2
4
2

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.