Inviting Politicians

Before the next parliamentary election the president is going to have a meeting with the top politicians of the country. But, as you know, our politicians are usually arrogant in nature and can’t tolerate opposition. So, if all of them are invited to the same meeting, they will ruin it (the same way they are ruining the country). However, from his past experience the president knows that he can always divide the politicians into four disjoint groups such that no two fighting politicians are placed in the same group. Then each of the four groups will be invited on a different day and thus avoiding any unpleasant situation. The president requests you to help him in solving the problem. Input The first line of the input contains an integer T (≤ 15) indicating the number of test cases to follow. The first line of each test case contains two integers N(≤ 300) and M(≤ 5000). Each of the next N lines contains the name of a politician. No name will be more than 10 characters long and will not contain any whitespace character. Each of the next M lines contains the name of two politicians (both of which are valid names occurring in the nameslist given at the beginning of the test case) who are not in good terms with each other and hence can not be placed in the same group. Output For each test case in the input first output the test case number (starting from 1) as shown in the sample output. Then for each i(= 1, 2, 3, 4) print an integer Pi on line 2i indicating the number of politicians to be invited on day i, and on line 2i + 1 print the names of those politicians with every two consecutive names separated by a single whitespace character. Assume that the politicians can always be invited in 4 days and can never be invited in less than 4 days. Note that the solution is not unique and hence any valid solution is acceptable. Print a blank line between two consecutive test cases. Sample Input 2 46 A B C D AB AC AD BC BD CD 67 A B C

2/2 D E F AB AC AD BC BD CD DE Sample Output Case #1 1 A 1 B 1 C 1 D Case #2 2 AE 1 B 1 C 2 DF