Рассадка гостей на тое
На той в Таласе пригласили 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.
Комментарии