50098. Disjoint Clubs

I'm a slow walker, but I never walk backwards.

Write a program to pick the clubs that have no member in common.

Task Description

There are N clubs for 64 persons to join. Each person has an id from 0 to 63. Each person can join as many clubs as he wishes. After people join the clubs, you need to pick K clubs so that no two clubs have any person in common. That is, the member list of any two chosen clubs are disjoint. For example, if we have five clubs A, B, C, D and E. The following are the member list for each club:

club id club name member list
0 club A 6, 7, 9
1 club B 11, 13, 17
2 club C 6, 13, 15
3 club D 0, 4, 5, 8, 33, 63
4 club E 10

The members of club A and club B are disjoint since they do not have any common member. However, the members of club A and club C are not disjoint since they have common member 6. Thus, we have four clubs A, B, D, E whose members are disjoint.

Note that we need to choose K clubs in alphabetic (dictionary) order if there are more than one solutions. For example, if K = 4, obviously we have only one solution (A, B, D, E). If K = 3, we have four solutions (A, B, D), (A, B, E), (A, D, E), (B, D, E) and we will choose the solution (A, B, D) since it has the least alphabetic order.

Write a program to pick out K clubs that have no member in common, and output K clubs with their id which is from 0 to N-1. It is guaranteed that there exists a solution.

Subtask

  • 20 points: K = 2.
  • 40 points: K > 2.
  • 40 points: N and K are very large and you will get TLE if you do not use bit operations. Note that it is very straightforward to represent a set of people as a long long unsigned integer. Then it is also straightforward to efficiently check whether two sets of people are disjoint using bit operations. Also you need to solve this problem recursively. You need to determine whether you should pick a club. What parameters should be changed for the recursion if you do choose this club, and what parameters should be changed if you do not choose this club?

Input Format

The input contains only one test case. The first line contains two integers N and K, where N is the number of the clubs, and K is the number of disjoint clubs we will pick. The rest of input are the member information for each club. Each line contains a sequence of integers. The first integer M in each line is the number of members, and it is followed by the member list of the club. It is guaranteed that there is at least one member for each club.

  • N < 101
  • 1 < K <= N
  • M < 65

Output Format

Print ids of K clubs which have no member in common. Note that the id number should be print in increasing order.

Sample Input 1

5 2
3 6 7 9
3 11 13 17
3 6 13 15
6 0 4 5 8 33 63
1 10

Sample Output 1

0
1

Sample Input 2

5 3
3 6 7 9
3 11 13 17
3 6 13 15
6 0 4 5 8 33 63
1 10

Sample Output 2

0
1
3

Sample Input 3

82 24
5 31 33 42 44 53
1 59
7 29 37 42 43 44 50 58
10 3 10 18 24 32 39 46 50 56 60
1 10
1 29
10 2 11 17 27 31 39 49 50 55 63
2 16 18
2 57 61
7 30 32 35 45 47 49 59
2 18 20
2 16 17
7 33 40 43 51 57 59 62
5 28 32 40 48 57
1 7
1 56
1 37
3 51 52 62
12 19 23 26 29 30 35 36 43 45 55 60 61
6 32 35 42 51 54 59
6 29 38 44 49 52 62
1 16
2 49 51
8 24 27 30 34 41 49 50 57
4 44 46 55 59
10 17 24 26 27 31 32 38 44 46 55
2 57 58
4 42 49 51 53
1 54
11 3 9 13 19 24 29 35 45 52 55 60
1 4
9 19 26 29 33 39 45 50 54 58
5 44 46 48 58 63
2 10 14
2 53 58
2 7 12
9 21 22 23 32 37 41 45 51 60
11 9 19 23 31 36 41 45 55 57 58 59
1 59
8 29 39 42 46 56 58 59 62
3 54 60 63
1 50
3 43 53 59
2 48 52
2 24 25
3 51 61 62
1 28
5 27 37 45 55 59
8 13 22 24 33 39 49 55 62
11 5 15 20 22 24 31 39 49 52 59 63
2 32 35
4 37 41 45 55
12 6 7 17 18 26 28 35 44 47 50 56 58
3 48 52 59
1 29
1 12
2 19 23
11 14 19 28 31 33 35 37 43 51 58 59
9 15 16 21 31 38 47 48 54 56
1 63
7 16 22 30 37 44 47 55
6 29 39 44 47 54 63
1 29
1 61
7 49 52 53 56 58 61 62
3 39 47 55
2 52 59
5 38 44 47 55 57
7 25 31 39 49 57 59 61
4 37 47 53 63
5 53 57 59 60 63
11 0 1 10 12 17 20 30 40 42 51 61
4 52 56 57 63
1 60
3 37 44 48
7 34 38 40 43 53 59 63
5 48 49 53 54 61
5 39 43 50 54 62
8 41 42 44 49 50 54 55 59
2 62 63
1 42
12 5 11 15 17 22 30 31 41 48 51 58 60

Sample Output 3

0
1
4
5
10
11
14
15
16
22
26
28
30
41
43
44
46
50
55
56
59
63
65
73

Discussion