Задача D. Уровни доступа

Автор:С. Пак   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

В сверхсекретной лаборатории вооруженных сил галактического альянса работают N сотрудников и имеется M кабинетов. Недавно все двери лаборатории были оборудованы магнитными замками, которые открываются специальными магнитными ключами. Перед руководством лаборатории встала задача организации доступа сотрудникам в соответствующие их правам кабинеты.

Все кабинеты пронумерованы по порядку, начиная с нуля. В реестре для каждого сотрудника указаны номера кабинетов, в которые он может попасть по своему ключу. В ключ каждого сотрудника и замок каждого кабинета будет записан некоторый уровень доступа. Уровни доступа — числа, идущие по порядку, начиная с нуля. Сотрудник сможет зайти в кабинет, если его уровень доступа больше или равен уровню доступа кабинета.

Необходимо назначить уровни доступа таким образом, чтобы каждый сотрудник имел доступ только в те кабинеты, в которые он может попасть согласно реестру, и при этом общее количество уровней доступа было как можно меньше.

Рекомендуется рассмотреть частичные решения.

Формат входного файла

В первая строка входного файла содержит целые числа N и M. Каждая из следующих N строк описывает права доступа одного сотрудника и содержит целое число Ki —количество доступных сотруднику кабинетов, за которым следует Ki различных целых чисел — номера кабинетов.

Каждый сотрудник имеет доступ к хотя бы одному кабинету, однако некоторые кабинеты могут остаться неиспользованными.

Формат выходного файла

Первая строка выходного файла должна содержать целое число L — количество разных уровней доступа. Следующие L строк должны содержать описания уровней. Каждая из этих строк соответствует очередному уровню доступа и должна содержать целое число Di ≥ 1, за которым следует строго возрастающая последовательность из Di целых чисел — номера кабинетов, доступных на этом и последующих уровнях, но недоступных на предыдущих уровнях.

Если решения не существует, выведите единственное число 1.

Ограничения

1 ≤ N, Ki ≤ 2000, 1 ≤ M ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
2 0 1
3 0 2 1
3 2 1 0
2
2 0 1
1 2
2
3 3
1 0
1 1
1 2
-1

0.044s 0.008s 15