C. Вирусы
ограничение по времени на тест
0.75 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Комитет по Исследованию Двоичных Вирусов открыл способ репродукции широкой семьи вирусов, генетический код которых состоит из нулей и единиц. Каждый вирус возникает из одного гена; для простоты, гены обозначены целыми числами от $$$0$$$ до $$$G - 1$$$. В любой момент времени вирус представляет собой цепочку генов. Когда происходит мутация, один из генов в цепочке заменяется на одну из цепочек генов в соответствии с таблицой мутаций. Вирус прекращает мутировать, когда он состоит только из генов $$$0$$$ и $$$1$$$.

Например, при следующей таблице мутации: $$$$$$ 2 \to \langle 0\ 1 \rangle \\ 3 \to \langle 2\ 0\ 0\rangle\\ 3 \to \langle 1\ 3\rangle\\ 4 \to \langle 0\ 3\ 1\ 2\rangle\\ 5 \to \langle 2\ 1\rangle\\ 5 \to \langle 5\rangle $$$$$$ вирус, который изначально состоял из одного гена $$$4$$$, мог мутировать так: $$$$$$ \langle 4 \rangle \to \langle \underline{0\ 3\ 1\ 2} \rangle \to \langle 0\ \underline{2\ 0\ 0}\ 1\ 2 \rangle \to \langle 0\ \underline{0\ 1}\ 0\ 0\ 1\ 2 \rangle \to \langle 0\ 0\ 1\ 0\ 0\ 1\ \underline{0\ 1} \rangle $$$$$$ или же другим образом: $$$$$$ \langle 4 \rangle \to \langle \underline{0\ 3\ 1\ 2} \rangle \to \langle 0\ \underline{1\ 3}\ 1\ 2 \rangle \to \langle 0\ 1\ 3\ 1\ \underline{0\ 1} \rangle \to \langle 0\ 1\ \underline{2\ 0\ 0}\ 1\ 0\ 1 \rangle \to \langle 0\ 1\ \underline{0\ 1}\ 0\ 0\ 1\ 0\ 1 \rangle $$$$$$

Вирусы выявляются антителами, которые обнаруживают присутствие конкретных последовательностей нулей и единиц в коде вирусов. Например, антитело, которое реагирует на последовательность $$$\langle 0\ 0\ 1\ 0\ 0 \rangle$$$, обнаружит вирус $$$\langle 0\ 0\ 1\ 0\ 0\ 1\ 0\ 1 \rangle$$$, но не обнаружит вирус $$$\langle 0\ 1\ 0\ 1\ 0\ 0\ 1\ 0\ 1 \rangle$$$.

Для каждого гена от $$$2$$$ до $$$G-1$$$, учёные хотят знать, достаточно ли данного множества антител, чтобы обнаружить все вирусы, которые могут мутировать из этого гена. Если нет, то они хотят знать длину кратчайшего вируса, который невозможно обнаружить.

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

Входные данные

В первой строке ввода даны три целых числа $$$G$$$, $$$N$$$ и $$$M$$$ ($$$G > 2$$$, $$$N \geq G - 2$$$, $$$M \geq 0$$$), количество генов, количество строк в таблице мутаций и количество антител, соответсвенно.

Следующие $$$N$$$ строк содержат описания строк в таблице мутаций; в начале каждой строки даны два целых числа $$$a$$$ и $$$k$$$ ($$$2 \leq a < G$$$, $$$k \geq 1$$$), за которыми следуют $$$k$$$ целых чисел $$$b_1, b_2, \ldots, b_k$$$ ($$$0 \leq b_i < G$$$), которые описывают строку $$$$$$ a \to \langle b_1\ b_2\ \ldots\ b_k \rangle $$$$$$

Сумма всех значений $$$k$$$ не превышает $$$100$$$. Каждое целое число от $$$2$$$ до $$$G - 1$$$ появляется в таблице как $$$a$$$ по крайней мере один раз.

Следующие $$$M$$$ строк содержат описание антител; каждая из этих строк содержит целое число $$$\ell$$$ ($$$\ell \geq 1$$$), за которым следуют $$$\ell$$$ целых чисел $$$c_1, c_2, \ldots, c_\ell$$$ ($$$0 \leq c_i \leq 1$$$), которые описывают антитело. Сумма всех значений $$$\ell$$$ не превышает $$$50$$$.

Выходные данные

Ваша программа должна вывести ровно $$$G - 2$$$ строк с ответами для каждого гена от $$$2$$$ до $$$G - 1$$$ в такой последовательности.

Если с помощью данных антител возможно обнаружить все вирусы, которые могут появиться в результате мутаций из конкретного гена, выведите слово «YES». Это нужно вывести также и тогда, если из данного гена не может появиться ни один вирус (такое может случиться также и тогда, если цепочка никогда не перестаёт мутировать).

Иначе выведите слово «NO», за которым выведите длину кратчайшего вируса, который невозможно обнаружить. Гарантируется, что это значение во всех тестовых примерах меньше, чем $$$2^{63}$$$.

Система оценки

Подзадачи:

  1. (11 баллов) Без антител ($$$M = 0$$$)
  2. (14 баллов) $$$N = G - 2$$$
  3. (25 баллов) Одно антитело ($$$M = 1$$$)
  4. (32 баллов) Сумма всех значений $$$\ell$$$ не превышает $$$10$$$
  5. (18 баллов) Без дополнительных ограничений.
Пример
Входные данные
6 6 2
2 2 0 1
3 3 2 0 0
3 2 1 3
4 4 0 3 1 2
5 2 2 1
5 1 5
2 1 1
5 0 0 1 0 0
Выходные данные
NO 2
NO 4
NO 9
YES