Party with Enemies#10994
Consider a party planning scenario. There is a group of people to choose from, but some pairs among them are mutual enemies. To organize a pleasant gathering, you want to invite people such that nobody attends together with anyone they are an enemy with, and every person will only attend if all their friends are also invited, while none of their enemies are.
The “enemy” relationship has the following properties:
Anti-transitive. If is an enemy of , and is an enemy of , then is a friend of . Also, the enemies of the friends of are his enemies, and the friends of the friends of are his friends.
Symmetrical. If is an enemy of , then is an enemy of (although it may not be indicated in his list of enemies).
One person will accept an invitation to the party if, and only if, they are invited, all their friends are invited, and none of their enemies is invited. You have to find the maximum number of people that can be invited, so that all of them accept their invitation.
For instance, if n = 5, and we know that: is enemy of , is enemy of , and is enemy of , then we could invite a maximum of people. These people could be and , but for this problem we only want the number of people invited.
The first line contains the number of test cases. A blank line follows this number, and a blank line is also used to separate test cases. The first line of each test case contains an integer n~(n \le 200), indicating the number of people who have to be considered. For each of these people, there is a line with their list of enemies. The first line contains the list of enemies of person , the second line contains the list of enemies of person , and so on. Each list of enemies starts with an integer (the number of known enemies of that person) and then, there are integers (the enemies of that person). So, for example, if a person’s enemies are and , their list of enemies would be: .
For each test case, output a single line containing an integer — the maximum number of people who can be invited, so that all of them accept their invitation.
Example 1