Montesco vs Capuleto
Romeo and Juliet have finally decided to get married. But preparing the wedding party will not becso easy, as it is well-known that their respective families - the Montesco and the Capuleto - are bloody enemies. In this problem you will have to decide which person to invite and which person not to invite, in order to prevent a slaugther.
We have a list of n people who can be invited to the party or not. For every person i, we have a list of his enemies:
e2, . . . ,
ep. The “enemy” relationship has the following properties:
- Anti-transitive. If a is an enemy of b, and b is an enemy of c, then a is a friend of c. Also, the enemies of the friends of a are his enemies, and the friends of the friends of a are his friends.
- Symmetrical. If a is an enemy of b, then b is an enemy of a (although it may not be indicated in his list of enemies).
One person will accept an invitation to the party if, and only if, he is invited, all his friends are invited and none of his 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: 1 is enemy of 3, 2 is enemy of 1, and 4 is enemy of 5, then we could invite a maximum of 3 people. These people could be 2, 3 and 4, but for this problem we only want the number of people invited.
The first line contains the number m of test cases in this file. 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, indicating the number of people who have to be considered. You can assume that n ≤ 200. For each of these n people, there is a line with his list of enemies. The first line contains the list of enemies of person 1, the second line contains the list of enemies of person 2, and so on. Each list of enemies starts with an integer p (the number of known enemies of that person) and then, there are p integers (the p enemies of that person). So, for example, if a person’s enemies are 5 and 7, his list of enemies would be: 2 5 7.
For each test case, the output should consist of a single line containing an integer, the maximum number of people who can be invited, so that all of them accept their invitation.
3 5 1 3 1 1 0 1 5 0 8 2 4 5 2 1 3 0 0 0 1 3 0 1 5 3 2 2 3 1 3 1 1
3 5 0