MENMARS - Men From Mars

Beings (men) living on Mars discovered that there are beautiful beings (women) living on Venus.  Men decided to change their life and want to travel using their spaceships to Venus to start a new life style. Unfortunately, women love connections and relationships and they won’t let a group of spaceships pass to their planet unless the number of spaceships in one of the “fully coupled” subgroups exceeds a certain minimum threshold. A fully coupled/connected group of spaceships is a group with each pair of spaceships can communicate together.

The spaceships and their airport on mars are very complicated. First, a spaceship communicates with another spaceship only if a command from the airport headquarter is issued. Second, the airport is a small one that can launch at a time a group of maximum K spaceships, connected in a random way. There are 2 types of commands that can be issued from headquarter to manage the spaceships connections: 1) Flip command for a group that establishes a new communication between every pair of disconnected spaceships and disconnect every previously connected pair of spaceships in the group, 2) Merge command for some of the groups to let them be one group, but no communications/connections modifications happen.

Unfortunately, under these constraints we can’t launch all spaceships in a fully coupled state that satisfies women. So, the Men developed an automatic software that will issue commands to launch the spaceships in groups, then will issue commands (Flip, Merge) in a way that hopefully produces at least one of the fully connected subgroups with maximum number of spaceships that satisfies women so that they pass to Venus.

Given the groups of spaceships and the issued commands for them, you have to calculate the maximum number of spaceships that are fully coupled in the final group.

Input Specification:

The first line of input contains an integer T that represents the number of test cases, then follow T test cases. Each test case start with a line with N (the number of spaceships - 1 ≤ N ≤ 1000), M (the number of launch groups - 1 ≤ M ≤ 1000). Then M lines follow, one for each group: starting with K (number of spaceships in the group 1 ≤ K ≤ 10), E (number of connections in the group), and then E pair of numbers representing bidirectional connection between 2 spaceships: space_ship_id1, space_ship_id2 where 0 ≤ space_ship_id1, space_ship_id2 < K. The m-th group has id (m-1).

Then Set of commands are given, each one on a line. Flip command on format “F group_id” to flip the group with given group id. Merge Command on format “M T group_id_1, group_id_2… group_id_T” that merges T groups and let their new id to be the maximum id of the merged groups.

 

Output Specification:

For each test case, output a single line of output in the form “Case K: T” where K is the number of the test case and T is the maximum number of spaceships that are fully coupled in the final group. Check sample below for the format.

Sample input:

1

7 4

3 3 0 1 0 2 1 2

2 1 0 1

1 0

1 0

F 1

M 2 1 2

F 0

M 2 0 2

F 2

M 2 3 2

*

Sample Output:

Case 1: 6

Sample Explanation

In this example we have 7 spaceships in 4 groups. First group (id = 0) is forming a triangle shape, second is segment shape, third is isolated spaceship and forth (id = 3) is also isolated. The first command flips the second group to 2 isolated spaceships. The second command merge 2 groups, id =2 to have 3 isolated spaceships with new. The third command flips first group to 3 isolated spaceships. The fourth one merges them under one group of 6 isolated group with id = 2. The fifth command flips this group to a fully coupled group of 6 spaceships. Finally a merge for that group with the fourth group and we have a new group with id = 3 of 6 spaceships fully connected and 1 isolated node.


Added by:Mostafa Saad Ibrahim
Date:2011-11-13
Time limit:0.808s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:10th Egyptian Collegiate Programming Contest

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.