Мориарти поймал n человек в n различных комнатах гостиницы. Двери в некоторые комнаты заперты, в остальные открыты. Однако, существует условие, что люди могут спастись только когда все двери будут открыты одновременно. Есть m переключателей. Каждый переключатель контролирует двери в некоторые комнаты, однако, каждая дверь контролируется ровно двумя переключателями.
Вам дано изначальное положение каждой двери. При изменении положения любого переключателя, то есть при включении его, когда он выключен, или выключении, когда он включен, меняется положение каждой двери, которые контролирует этот переключатель. Например, мы изменили положение переключателя 1, который подключен к дверям 1, 2, и 3, которые были в состояниях заперто, открыто и открыто. Тогда их состояния изменятся на открыто, закрыто и закрыто, соответственно.
Ваша задача сказать Шерлоку, существует ли способ открыть все двери одновременно.
Выходные данные
Выведите "YES" без кавычек, если возможно открыть все двери одновременно, иначе выведите "NO" без кавычек.
Примечание
Во втором примере изначальные состояния дверей равны [1, 0, 1] (0 — закрыта, 1 — открыта).
После переключения переключателя 3, мы получаем [0, 0, 0], что значит, что все двери закрыты.
Затем, после переключения переключателя 1, мы получим [1, 1, 1], что значит, что все двери открыты.
Можно показать, что в первом и третьем примере невозможно открыть все двери одновременно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 0 1
2 1 3
2 1 2
2 2 3
|
NO
|
|
2
|
3 3
1 0 1
3 1 2 3
1 2
2 1 3
|
YES
|
|
3
|
3 3
1 0 1
3 1 2 3
2 1 2
1 3
|
NO
|