Call Me Maybe
InterviewTime limit2sMemory limit1024 MB
For each lyric word, pick speech occurrences in round-robin order, or report NOT POSSIBLE if any lyric word never appears in the speeches.
Problem
The popular song "Call Me Maybe" by Carly Rae Jepson has recently been spoofed with great comedic success on the internet. In particular, one YouTube video splices words from different speeches by President Obama to string together the lyrics of the song. (Rumor has it that Angela Merkel is eagerly awaiting Mr. Obama's call.) You have decided that this idea is comic gold. Given a library of a particular person's speeches and the lyrics to a song, you want to spoof them by writing a program that checks the text of all the speeches and makes the appropriate word substitutions from the speeches to the song lyrics. For example, the first line of "Call Me Maybe" is "I threw a wish in the well." Perhaps "I" appears as the 10th word in speech number 4, "threw" appears as the 54th word in speech number 12, and so on. Of course, if the speaker never said "wish" in any of his speeches, then the spoof is not possible.
Given a list of speeches by an individual and the text of a song, determine whether the spoof is possible and, if so, list which word in which speech to use as each substitute.
To get a unique answer, cycle through each occurrence of a word in the set of speeches, in order by speech and word. If "I" appears five times in the song and appears in these four places: (1) speech 2, word 7, (2) speech 4, word 12, (3) speech 4, word 50, (4) speech 5, word 1, then the first substitution comes from speech 2, the second from the 12th word of speech 4, the third from the 50th word of speech 4, the fourth from speech 5, and the fifth from speech 2 again. A word does not have to appear in the speeches as many times as it appears in the song, but it must appear at least once. A word may appear several times in a speech; those occurrences are used in order, before the first occurrence of that word in the next speech.
Input
The first line contains a single integer n (1 <= n <= 20), the number of spoofs to potentially create. Each input set follows. The first line of each set contains an integer m (1 <= m <= 100), the number of speeches with text. Each speech is stored on a single line. The first token on each line is an integer t (1 <= t <= 1000), the number of words in the speech. Each word consists of 1 to 20 lowercase letters. Words are separated by spaces, and there are no other characters on these lines.
The speeches are followed by a single line with the lyrics of the song to spoof. The first token is an integer l (1 <= l <= 50), the number of words in the lyrics. Each word consists of 1 to 20 lowercase letters. Words are separated by spaces, and there are no other characters on this line.
Output
For each spoof, first output "Spoof #i: " where i is the spoof number, starting at 1. If no spoof is possible, output the string "NOT POSSIBLE".
If a spoof is possible, starting on the next line, output w lines, where w is the number of words in the song to spoof. Each line contains two integers separated by one space: the speech number and the word number. Both are numbered starting at 1.
Leave a blank line after the output for each test case.