CF776D.The Door Problem

Moriarty has trapped n people in n distinct rooms in a hotel. Some rooms are locked, others are unlocked. But, there is a condition that the people in the hotel can only escape when all the doors are unlocked at the same time. There are m switches. Each switch control doors of some rooms, but each door is controlled by exactly two switches.

You are given the initial configuration of the doors. Toggling any switch, that is, turning it ON when it is OFF, or turning it OFF when it is ON, toggles the condition of the doors that this switch controls. Say, we toggled switch 1, which was connected to room 1, 2 and 3 which were respectively locked, unlocked and unlocked. Then, after toggling the switch, they become unlocked, locked and locked.

You need to tell Sherlock, if there exists a way to unlock all doors at the same time.

莫里亚蒂将 n 个人分别困在酒店的 n 个不同房间中。部分房间的门是锁着的，其余则是开着的。但有一个条件：酒店中的人只有在所有门同时处于解锁状态时才能逃脱。一共有 m 个开关，每个开关控制若干扇门，且每扇门恰好由两个开关控制。

你已知所有门的初始状态（锁着或开着）。切换任意一个开关（即：若其当前为关，则打开；若当前为开，则关闭），会改变该开关所控制的所有门的开关状态。例如：假设我们切换了开关 1，它连接着房间 1、2 和 3，而这三个房间的初始状态分别为“锁着”、“开着”、“开着”；那么切换开关 1 后，这三个房间的状态将变为“开着”、“锁着”、“锁着”。

你需要告诉夏洛克：是否存在一种开关切换方案，使得所有门最终同时处于解锁状态？

First line of input contains two integers n and m (2 ≤ n ≤ 105, 2 ≤ m ≤ 105) — the number of rooms and the number of switches.

Next line contains n space-separated integers _r_1, _r_2, ..., r__n (0 ≤ r__i ≤ 1) which tell the status of room doors. The i-th room is locked if r__i = 0, otherwise it is unlocked.

The i-th of next m lines contains an integer x__i (0 ≤ x__i ≤ n) followed by x__i distinct integers separated by space, denoting the number of rooms controlled by the i-th switch followed by the room numbers that this switch controls. It is guaranteed that the room numbers are in the range from 1 to n. It is guaranteed that each door is controlled by exactly two switches.

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$，$2 \leq m \leq 10^5$）——分别表示房间数量和开关数量。

第二行包含 $n$ 个用空格分隔的整数 $r_1,\ r_2,\ \dots,\ r_n$（$0 \leq r_i \leq 1$），表示各房间门的状态：若 $r_i = 0$，则第 $i$ 个房间的门被锁住；否则门处于解锁状态。

接下来的 $m$ 行中，第 $i$ 行首先给出一个整数 $x_i$（$0 \leq x_i \leq n$），随后是 $x_i$ 个互不相同的整数（以空格分隔），表示第 $i$ 个开关所控制的房间数目，以及这些房间的编号。保证所有房间编号均在 $1$ 到 $n$ 的范围内。保证每个房间门恰好由两个开关控制。

Output "YES" without quotes, if it is possible to open all doors at the same time, otherwise output "NO" without quotes.

如果可以同时打开所有门，则输出不带引号的 "YES"，否则输出不带引号的 "NO"。

In the second example input, the initial statuses of the doors are [1, 0, 1] (0 means locked, 1 — unlocked).

After toggling switch 3, we get [0, 0, 0] that means all doors are locked.

Then, after toggling switch 1, we get [1, 1, 1] that means all doors are unlocked.

It can be seen that for the first and for the third example inputs it is not possible to make all doors unlocked.

在第二个样例输入中，门的初始状态为 [1, 0, 1]（0 表示锁定，1 表示解锁）。

切换开关 3 后，得到 [0, 0, 0]，即所有门均被锁定。

接着，切换开关 1 后，得到 [1, 1, 1]，即所有门均被解锁。

可以看出，对于第一个和第三个样例输入，无法使所有门均被解锁。