Роздiл майна
Роздiл майна
У Сема i Юри є n кошикiв з яблуками. Всього є m видiв яблук. В i-му кошику є ci
яблук, вид j-го яблука в i-му кошику — aij
.
Сем i Юра посварились мiж собою i хочуть подiлити кошики так, щоб:
- Кожен отримав хоча б один кошик.
- Не iснувало жодного виду яблука, яке б було i в Сема, i в Юри.
Допоможiть їм подiлити кошики.
Формат вхiдних даних
Перший рядок мiстить два цiлi числа n та m (**2 ⩽ n ⩽ 105
, 1 ⩽ m ⩽ 105
**) — кiлькiсть кошикiв з яблуками та види яблук вiдповiдно.
Наступнi 2n рядкiв мiстять описи кошикiв. Опис кожного кошика у двох рядках. Перший рядок
мiстить одне цiле число ci
(**1 ⩽ ci
⩽ 2 ∙ 105
**). Другий рядок мiстить ci цiлих чисел ai1
; ai2
; : : : ; aici
(**1 ⩽ aij
⩽ m**) — вид яблука.
Гарантується, що сума всiх ci
не перевищує 2 ∙ 105
.
Формат вихiдних даних
Виведiть «YES», якщо можливо роздiлити кошики, або «NO» у протилежному випадку.
Якщо вiдповiдь «YES», також у другому рядку виведiть n цiлих чисел 1 або 2. Якщо i-те число рiвне 1, то i-ий кошик повинен дiстатись Сему, якщо 2 — Юрi.
Якщо iснує декiлька можливих вiдповiдей, виведiть будь-яку.
4 7 4 1 3 7 2 2 5 6 1 6 2 7 3
YES 1 2 2 1
2 2 2 1 2 1 1
NO