| H - Foes of Friends |
You are organizing a party and you want to invite as many friends as possible. However, some of your friends hold grudges against other of your friends, and you don't want to invite two persons to the party if any of them considers the other an enemy.
For example, if Alice hates Bob, Bob hates Alice and Carol, Carol hates Bob and Ed, Daniel does not hate anyone, and Ed hates Carol, then you can invite Alice, Carol and Daniel at the same time, but not Alice, Bob and Daniel.
Since you haven't yet decided who to invite but need to know how much food to buy, you decide to write a program to calculate the maximum number of friends that can be invited to the party.
The input format is as follows:
An integer in a single line which says the number of problems to solve. Then, for each problem:
An integer in a single line indicating the number of friends (n). Then, for each friend i (starting at 0):
An integer indicating the number of enemies of this friend (e), followed by e integers (jk), each one meaning that the friend number i considers the friend number jk an enemy. All integers are separated by spaces.
n is less than 200 and e is less than 100.
For each problem, a line with a single number indicating the maximum number of friends that can be invited at the same time.
2
10
0
0
2 4 6
1 4
1 3
0
1 2
0
0
0
45
7 20 26 31 35 39 40 41
0
12 9 11 12 16 20 21 31 32 35 36 40 41
3 9 20 21
7 9 11 20 21 31 32 41
0
12 9 10 11 12 15 16 20 26 31 35 40 41
10 9 16 17 19 20 21 29 38 41 43
7 9 17 18 19 20 21 22
12 2 3 4 6 7 8 26 31 35 39 40 41
5 6 21 32 36 39
9 2 4 6 21 26 35 39 40 41
7 2 6 21 26 32 39 40
0
0
7 6 21 27 32 36 39 43
15 2 6 7 17 21 22 24 25 26 32 33 36 37 39 40
9 7 8 16 33 34 37 38 40 41
1 8
5 7 8 33 34 41
7 0 2 3 4 6 7 8
15 2 3 4 7 8 10 11 12 15 16 26 31 35 40 41
7 8 16 29 34 38 41 43
0
3 16 40 41
2 16 40
9 0 6 9 11 12 16 21 32 36
1 15
0
5 7 22 33 37 40
1 41
6 0 2 4 6 9 21
10 2 4 10 12 15 16 26 35 40 41
7 16 17 19 29 38 41 43
3 17 19 22
7 0 2 6 9 11 21 32
6 2 10 15 16 26 40
4 16 17 29 43
4 7 17 22 33
7 0 9 10 11 12 15 16
15 0 2 6 9 11 12 16 17 21 24 25 29 32 36 43
15 0 2 4 6 7 9 11 17 19 21 22 24 30 32 33
0
6 7 15 22 33 37 40
0
8
22