Рассадка гостей на тое


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

На той в Таласе пригласили n гостей. Каждого нужно посадить либо на сторону жениха (обозначим 0), либо на сторону невесты (1). Родственники передали m пожеланий. Каждое пожелание имеет вид «гость i сидит на стороне x или гость j сидит на стороне y» — должно выполняться хотя бы одно из двух (может быть i = j).

Тамада записывает рассадку строкой из n символов 0 и 1: символ номер i — сторона гостя i. Найдите рассадку, при которой выполняются все пожелания, а если таких несколько — лексикографически наименьшую строку (тамада больше любит сторону жениха и старших гостей с маленькими номерами).

Рисунок

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

В первой строке — два целых числа n и m (1 ≤ n ≤ 2000, 1 ≤ m ≤ 5000). В каждой из следующих m строк — четыре целых числа i x j y (1 ≤ i, j ≤ n, x, y ∈ {0, 1}).

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

Выведите искомую строку или NO, если выполнить все пожелания нельзя.

Пример 1

Вход:

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

Выход:

010

Пояснение

Строки 000 и 001 не подходят: в первой нарушено пожелание «2 на стороне 1 или 3 на стороне 1», во второй — «1 на стороне 1 или 3 на стороне 0». Строка 010 подходит.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n ≤ 12.


Комментарии

Еще нет ни одного комментария.