407874: GYM102911 J Junior Prom

Everyone is excited to celebrate the new year and the (eventual) end of the pandemic with a bombastic Junior Prom! Unfortunately, people are a little too excited for it, and each student organization decided to host their own prom—plus, they all scheduled them to happen on the same weekend! This is a logistical nightmare for officers who are part of multiple orgs, since their presence is required at each of their org's events.

Alice has been enlisted to help resolve these scheduling conflicts.

There are $$$N$$$ students in the batch and $$$M$$$ different orgs that are holding a prom. The Office of Student Activities has given Alice the full list of officers of each org. Each org requires all of its officers to be present at its prom in order for it to run smoothly. Unfortunately, this might cause conflicts if the same member is needed at multiple different events. Since prom lasts until late into the evening, it is impossible for the same student to attend two different events if they both occur on the same night. The only leeway we have for rescheduling is that for each event, we can decide whether it will happen on Saturday or Sunday.

Alice must resolve these scheduling conflicts. For each of the org events, she must assign a date to it (either Saturday or Sunday) such that all org officers can attend their respective events with no conflict, or report that this is impossible. If there are multiple such valid assignments, choose any such that the maximum number of possible events are held on Saturday.

Help Alice out?

The first line of input contains two space-separated integers $$$N$$$ and $$$M$$$, the number of students and the number of orgs that are holding proms.

Each org is described with two lines (so $$$2M$$$ lines of input follow). The first line contains a single integer $$$r_i$$$, the number of officers in the $$$i$$$th org. The second line contains $$$r_i$$$ space-separated strings, where each string is the name of an officer of that org.

Contestants are recommended to use fast methods of input and output for this problem.

If the task is impossible, output NO on a single line. Otherwise, output YES.

If YES, output $$$M$$$ more lines describing when the prom of each org is scheduled. The $$$i$$$th line should contain the string Saturday if the prom of the $$$i$$$th org will be held on Saturday, and Sunday if it will be held on Sunday. The order of the orgs is the same as the order that they are given in the input.

If there are multiple solutions, output any such that the number of Saturday proms is maximized.

$$$1 \leq N \leq 2\cdot 10^5$$$

$$$1 \leq M \leq 2\cdot 10^5$$$

If $$$r_i$$$ is the number of members needed for the $$$i$$$th event, then $$$1 \leq \sum r_i \leq 4\cdot 10^5$$$.

Each student's name is distinct, consists only of upper or lower case letters, and is at most $$$4$$$ characters long.

The names in the list of officers for a particular org are all distinct, and each org has at least one officer.

At most $$$N$$$ distinct names will appear across all org officer lists.

Subtask 1 (25 points):

$$$M, N \leq 16$$$

$$$\sum r_i \leq 400$$$

Subtask 2 (25 points):

$$$\sum r_i \leq 400$$$

Subtask 3 (25 points):

$$$\sum r_i \leq 4000$$$

Subtask 4 (25 points):

No further constraints.

15 4
3
Dani Riri Vern
3
Dani Nate Chri
4
Luis Mark Rap Riri
5
Cis Fran Kev Kyle Vern

YES
Sunday
Saturday
Saturday
Saturday

16 5
3
Dani Joe JV
3
JV Lanc Lzro
3
Earl Nico Treb
3
Acad Joe Nico
3
Earl Karl Lzro

NO

In the first sample test case, we can show that there will be a conflict if we host all events on Saturday. However, if we host the first org event on Sunday and all other events on Saturday, then there will be no conflicts.

In the second sample test case, we can show by exhaustion that it is impossible to schedule the org events without there being at least one conflict.