Комитет по Исследованию Двоичных Вирусов открыл способ репродукции широкой семьи вирусов, генетический код которых состоит из нулей и единиц. Каждый вирус возникает из одного гена; для простоты, гены обозначены целыми числами от \(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 - 2\) строк с ответами для каждого гена от \(2\) до \(G - 1\) в такой последовательности.
Если с помощью данных антител возможно обнаружить все вирусы, которые могут появиться в результате мутаций из конкретного гена, выведите слово «YES». Это нужно вывести также и тогда, если из данного гена не может появиться ни один вирус (такое может случиться также и тогда, если цепочка никогда не перестаёт мутировать).
Иначе выведите слово «NO», за которым выведите длину кратчайшего вируса, который невозможно обнаружить. Гарантируется, что это значение во всех тестовых примерах меньше, чем \(2^{63}\).
Система оценки
Подзадачи:
- (11 баллов) Без антител (\(M = 0\))
- (14 баллов) \(N = G - 2\)
- (25 баллов) Одно антитело (\(M = 1\))
- (32 баллов) Сумма всех значений \(\ell\) не превышает \(10\)
- (18 баллов) Без дополнительных ограничений.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|