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

Условие

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

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

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

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

• N, K_i, M ≤ 100
• M ≤ 2000

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

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

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

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

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

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

Ограничения

1 ≤ N, K_i ≤ 2000, 1 ≤ M ≤ 10⁹

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

3 3
2 0 1
3 0 2 1
3 2 1 0

2
2 0 1
1 2

3 3
1 0
1 1
1 2

-1