Hide

# Problem ERA Duty Scheduler

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
Hide