Hide

Problem S
RA Duty Scheduler

/problems/dutyscheduler/file/statement/en/img-0001.jpg
Students hanging out with their resident advisors at Virginia Tech. Source: VT News

Resident Advisors (or RAs) at Virginia Tech are student leaders who are responsible for helping freshmen transition smoothly to college life. Mr. Friedel is trying to design a system to assist him in the process of scheduling RAs to be on duty every month. On each day there are exactly 2 RAs on duty. Unfortunately for Mr. Friedel, each RA is available only on specific days and can only be scheduled then. Before the end of each month, each RA submits a list of days with their availability to Mr. Friedel.

Your goal is to help him write a program that will take a list of RAs and their availabilities and assign two RAs for duty on each day.

While there is no limit for how many days each RA can be on duty, Mr. Friedel wants to reduce unfairness by limiting the imbalance between the number of days each RA is assigned.

Towards that goal, your program needs to minimize the maximum number of days to which any RAs may be assigned.

Input

The input consists of a single test case. The first line contains $2$ numbers $m$ ($2 \le m \le 60$) and $n$ ($28 \le n \le 31$) where $m$ is the number of RAs and $n$ is the total number of days this month. This is followed by $m$ lines where each line consists of the name of the RA followed by an integer $d$ ($1 \le d \le n$) denoting the number of days this RA is available. The remainder of the line consists of $d$ unique integers $i$ ($1 \le i \le n$) denoting the days on which this RA is available. Each RA’s name is a unique string between $1$ and $30$ characters consisting only of English lowercase or uppercase letters. You may assume that there is at least one possible assignment of RAs!

Output

On the first line, output the maximum number of days on which any RA is assigned. Following that, you should output $n$ lines starting with Day k: where $k$ is the number of the day ranging from $1$ to $n$ (inclusive and in order), followed by a space, followed by the names of two RAs scheduled for that day, separated by spaces. The two RAs scheduled for a given day can be listed in any order.

If there are multiple valid assignments, you may output any of them!

Sample Input 1 Sample Output 1
20 30
Katrina 11 1 3 4 8 10 12 13 15 17 27 29
Pawl 13 3 4 5 6 8 10 11 12 13 15 17 26 27
Sydney 14 1 2 3 4 6 7 8 11 13 14 15 16 28 30
Kylie 15 1 2 4 5 6 8 9 10 12 13 15 16 17 18 27
Meredith 15 1 2 4 7 8 9 11 12 13 25 26 27 28 29 30
Amanda 16 1 2 7 8 9 10 11 14 15 16 17 18 19 28 29 30
Akshay 16 1 2 3 4 6 7 8 12 13 14 15 16 17 28 29 30
Chelsea 17 1 2 3 4 5 7 8 9 11 15 16 17 25 27 28 29 30
Zachary 18 1 3 4 5 6 7 8 9 12 13 14 15 16 17 26 27 29 30
Alex 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 28 29 30
Tariq 19 1 3 4 5 6 8 10 11 12 13 18 19 20 22 24 25 26 27 29
Schlake 21 1 3 4 6 10 11 12 13 15 17 18 19 20 21 22 23 24 25 26 27 29
Joel 23 3 4 5 6 7 8 9 10 11 12 13 14 18 19 20 21 22 23 24 25 26 27 28
Benjamin 23 1 2 3 4 5 6 7 8 9 10 12 13 14 15 18 19 20 21 22 23 24 28 30
Collin 24 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 27 28 29 30
Austin 24 1 2 3 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 21 22 23 24 28 29
Shahmir 24 1 2 3 4 6 8 12 13 14 15 16 17 19 20 21 22 23 24 25 26 27 28 29 30
Harrison 25 1 2 3 6 7 8 9 10 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Josh 27 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 20 21 22 23 24 25 26 27 28 29 30
Amy 28 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
3
Day 1: Benjamin Katrina 
Day 2: Amanda Alex 
Day 3: Alex Katrina 
Day 4: Akshay Zachary 
Day 5: Collin Chelsea 
Day 6: Collin Schlake 
Day 7: Akshay Sydney 
Day 8: Pawl Meredith 
Day 9: Joel Kylie 
Day 10: Alex Amanda 
Day 11: Josh Meredith 
Day 12: Akshay Meredith 
Day 13: Schlake Sydney 
Day 14: Shahmir Amy 
Day 15: Kylie Katrina 
Day 16: Sydney Amanda 
Day 17: Amy Harrison 
Day 18: Collin Kylie 
Day 19: Harrison Tariq 
Day 20: Austin Benjamin 
Day 21: Amy Austin 
Day 22: Tariq Shahmir 
Day 23: Austin Joel 
Day 24: Benjamin Josh 
Day 25: Joel Tariq 
Day 26: Schlake Pawl 
Day 27: Harrison Pawl 
Day 28: Shahmir Josh 
Day 29: Chelsea Zachary 
Day 30: Zachary Chelsea 

Please log in to submit a solution to this problem

Log in