ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1107. Складская задача

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
На складе есть N различных видов товаров. Виды товаров занумерованы числами 1…N. Работники склада сделали K разных наборов из этих товаров. Будем говорить, что два набора “похожи”, если один из них получается удалением одного товара из другого набора или заменой одного товара на другой.
Например, набор “1 2 3 4” похож на наборы “3 2 1”, “1 2 5 3 4”, “1 2 3 4 2” и “1 5 4 3”, но не похож на наборы “1 2”, “1 1 2 2 3 4” и “4 5 3 6”.
Этот склад обслуживает M магазинов (0 < N < M < 101), посылая им наборы товаров. Любые два набора, посылаемые в один магазин, не должны быть похожи. Можно не посылать ни одного набора в какие-то из магазинов.
Напишите программу, которая определит, как распределить все K наборов по этим M магазинам.

Исходные данные

Первая строка содержит числа N, K и M. Затем следуют K строк, описывающих каждый набор товаров, K ≤ 50 000. Каждая из этих строк начинается количеством товаров в этом наборе, затем записаны номера товаров. Количество товаров в каждом наборе больше 0 и меньше 101. Все числа в этих строках разделяются ровно одним пробелом.

Результат

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

Пример

исходные данныерезультат
8 20 12
5 1 3 5 6 4
5 1 3 5 6 3
4 5 6 3 3
4 5 6 3 4
4 4 6 5 8
4 7 7 7 7
3 7 7 7
2 2 2
3 2 2 7
3 1 2 3
3 1 2 4
10 1 2 3 4 5 6 7 8 7 6
10 8 7 6 5 4 3 2 1 2 1
20 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 3 5 7
5 4 6 4 6 4
5 6 4 6 4 6
6 6 6 6 6 6 6
3 6 6 6
1 1
1 2
YES
2
1
9
1
6
2
4
5
3
7
8
5
4
8
7
9
1
1
2
3
Автор задачи: Дмитрий Филимоненков
Источник задачи: Tetrahedron Team Contest May 2001