Заданы n переключателей и m ламп. i-й переключатель включает некоторый поднабор ламп. Информация о них задана в виде матрицы a, состоящей из n строк и m столбцов, где ai, j = 1, если i-й переключатель включает j-ю лампу, и ai, j = 0, если i-й переключатель не подсоединен к j-й лампе.
В начале все m ламп выключены.
Переключатели изменяют состояние лампы только с «выключена» на «включена». Это значит, что если два или более переключателей подсоединены к одной лампе, то эта лампа включится, когда будет нажат любой из этих переключателей, и сохранит свое состояние даже если любой переключатель, подсоединенный к этой лампе, будет нажат позднее.
Гарантируется, что если нажать все n переключателей, то все m ламп окажутся включены.
Вы считаете, что у вас чересчур много переключателей, и хотели бы избавиться от одного из них.
Требуется сказать, существует ли такой переключатель, что если его не использовать, но нажать все остальные n - 1 переключателей, то все m ламп окажутся включены.
Выходные данные
Выведите «YES», если существует такой переключатель, что если его не использовать, но нажать все остальные n - 1 переключателей, то все m ламп окажутся включены. Выведите «NO», если нет такого переключателя.