# 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.

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.

• 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 23 6 7 93 11 13 173 6 13 156 0 4 5 8 33 631 10


## Sample Output 1

01


## Sample Input 2

5 33 6 7 93 11 13 173 6 13 156 0 4 5 8 33 631 10


## Sample Output 2

013


## Sample Input 3

82 245 31 33 42 44 531 597 29 37 42 43 44 50 5810 3 10 18 24 32 39 46 50 56 601 101 2910 2 11 17 27 31 39 49 50 55 632 16 182 57 617 30 32 35 45 47 49 592 18 202 16 177 33 40 43 51 57 59 625 28 32 40 48 571 71 561 373 51 52 6212 19 23 26 29 30 35 36 43 45 55 60 616 32 35 42 51 54 596 29 38 44 49 52 621 162 49 518 24 27 30 34 41 49 50 574 44 46 55 5910 17 24 26 27 31 32 38 44 46 552 57 584 42 49 51 531 5411 3 9 13 19 24 29 35 45 52 55 601 49 19 26 29 33 39 45 50 54 585 44 46 48 58 632 10 142 53 582 7 129 21 22 23 32 37 41 45 51 6011 9 19 23 31 36 41 45 55 57 58 591 598 29 39 42 46 56 58 59 623 54 60 631 503 43 53 592 48 522 24 253 51 61 621 285 27 37 45 55 598 13 22 24 33 39 49 55 6211 5 15 20 22 24 31 39 49 52 59 632 32 354 37 41 45 5512 6 7 17 18 26 28 35 44 47 50 56 583 48 52 591 291 122 19 2311 14 19 28 31 33 35 37 43 51 58 599 15 16 21 31 38 47 48 54 561 637 16 22 30 37 44 47 556 29 39 44 47 54 631 291 617 49 52 53 56 58 61 623 39 47 552 52 595 38 44 47 55 577 25 31 39 49 57 59 614 37 47 53 635 53 57 59 60 6311 0 1 10 12 17 20 30 40 42 51 614 52 56 57 631 603 37 44 487 34 38 40 43 53 59 635 48 49 53 54 615 39 43 50 54 628 41 42 44 49 50 54 55 592 62 631 4212 5 11 15 17 22 30 31 41 48 51 58 60


## Sample Output 3

01451011141516222628304143444650555659636573