D. Задача о дверях
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мориарти поймал n человек в n различных комнатах гостиницы. Двери в некоторые комнаты заперты, в остальные открыты. Однако, существует условие, что люди могут спастись только когда все двери будут открыты одновременно. Есть m переключателей. Каждый переключатель контролирует двери в некоторые комнаты, однако, каждая дверь контролируется ровно двумя переключателями.

Вам дано изначальное положение каждой двери. При изменении положения любого переключателя, то есть при включении его, когда он выключен, или выключении, когда он включен, меняется положение каждой двери, которые контролирует этот переключатель. Например, мы изменили положение переключателя 1, который подключен к дверям 1, 2, и 3, которые были в состояниях заперто, открыто и открыто. Тогда их состояния изменятся на открыто, закрыто и закрыто, соответственно.

Ваша задача сказать Шерлоку, существует ли способ открыть все двери одновременно.

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

Первая строка содержит два целых числа n и m (2 ≤ n ≤ 105, 2 ≤ m ≤ 105) — число комнат и число переключателей.

Следующая строка содержит n целых чисел r1, r2, ..., rn (0 ≤ ri ≤ 1) — изначальные состояния дверей. Комната i заперта, если ri = 0, иначе она открыта.

i-я из следующих m строк содержит целое число xi (0 ≤ xi ≤ n), а затем xi различных целых чисел — количество комнат, контролируемых i-м переключателем, а затем номера этих комнат. Гарантируется, что номера комнат — различные целые числа от 1 до n. Гарантируется, что каждая дверь контролируется ровно двумя переключателями.

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

Выведите "YES" без кавычек, если возможно открыть все двери одновременно, иначе выведите "NO" без кавычек.

Примеры
Входные данные
3 3
1 0 1
2 1 3
2 1 2
2 2 3
Выходные данные
NO
Входные данные
3 3
1 0 1
3 1 2 3
1 2
2 1 3
Выходные данные
YES
Входные данные
3 3
1 0 1
3 1 2 3
2 1 2
1 3
Выходные данные
NO
Примечание

Во втором примере изначальные состояния дверей равны [1, 0, 1] (0 — закрыта, 1 — открыта).

После переключения переключателя 3, мы получаем [0, 0, 0], что значит, что все двери закрыты.

Затем, после переключения переключателя 1, мы получим [1, 1, 1], что значит, что все двери открыты.

Можно показать, что в первом и третьем примере невозможно открыть все двери одновременно.