Заданы n переключателей и m ламп. i-й переключатель включает некоторый поднабор ламп. Информация о них задана в виде матрицы a, состоящей из n строк и m столбцов, где a_i, j = 1, если i-й переключатель включает j-ю лампу, и a_i, j = 0, если i-й переключатель не подсоединен к j-й лампе.

В начале все m ламп выключены.

Переключатели изменяют состояние лампы только с «выключена» на «включена». Это значит, что если два или более переключателей подсоединены к одной лампе, то эта лампа включится, когда будет нажат любой из этих переключателей, и сохранит свое состояние даже если любой переключатель, подсоединенный к этой лампе, будет нажат позднее.

Гарантируется, что если нажать все n переключателей, то все m ламп окажутся включены.

Вы считаете, что у вас чересчур много переключателей, и хотели бы избавиться от одного из них.

Требуется сказать, существует ли такой переключатель, что если его не использовать, но нажать все остальные n - 1 переключателей, то все m ламп окажутся включены.