Задача Case
Как известно, люди часто имеют сразу несколько увлечений. Например, один и тот же человек может выступать на олимпиаде по программированию, играть в любительском театре и ходить в туристические походы. Пусть количество возможных увлечений равняется m и все эти увлечения пронумерованы числами от 1 до m. Гарантируется, что для каждого из
m увлечений существует своя «группа по интересам», каждый человек принадлежит хотя бы к одной из групп и к каждой из
m групп принадлежит хотя бы один человек.
Однажды Начальник-Запрещальник решил, что m групп — слишком много, назначил некоторое время "Ч" и велел собраться представителям каждой группы в отдельном
обусловленном месте. Если на каком-то из обусловленных мест никого не окажется, Начальник-Запрещальник даст себе волю и запретит соответствующую группу. В такой ситуации нельзя, чтобы каждый
действовал сам по себе, не советуясь с другими. Поэтому люди решили договориться между собой. Понятно, что никто не пойдет поддерживать группу, которой не принадлежит. Но каждый согласен выбирать одну из своих групп так,
дабы ни одна из групп не была запрещена. Напишите программу, которая найдет способ распределить людей по указанным Начальником-Запрещальником местам (или сообщит, что
это невозможно). Достаточно добиться (если возможно), чтобы на каждое место пришел хотя бы один
человек. Если есть несколько разных способов, которые позволяют спасти все группы от
запрета, программа должна вывести любой из их.
Технические условия. Программа читает с клавиатуры количество групп
m (2 ≤ m ≤ 150), количество
человек n (m ≤ n ≤ 200), далее
n блоков такой структуры: первое число блока Кі - количество групп, к которой принадлежит
і-й человек (1 ≤ Кі ≤ m), потом заданные
Кі номеров тех групп, к которым он принадлежит (в порядке
возрастания). Все входные данные записаны в одной строке через
пробелы. Начальник-Запрещальник не принадлежит ни к одной из m
групп и не является ни одним из упомянутых n человек.
Программа должна вывести
на экран сначала 1,
если сохранить все группы можно, или 0, если нет. В случае
ответа 1, дальше нужно вывести в этой же строке n чисел значением от 1 до m
каждое, которые обозначают, на собрания какой группы пойдет соответствующий
(1-й, 2-й, ... , n‑й) человек. Если есть несколько разных распределений,
которые дают возможность спасти все группы от запрещения, выводите любое.
Примеры
Ввод
3 3 1 1 1 1 2 2 3
Вывод
0
Ввод
3 4 1 1 2 2 3 1 3 2 1 3
Вывод
1
1 2 3 1