← 返回题目列表

Codeforces · 776/D

D. 门问题

中文机器翻译题面 查看原题

Moriarty 将 n 个人困在酒店的 n 个不同的房间里。有些房间是锁着的,有些房间是不锁的。但是,有一个条件,酒店里的人只有在所有门同时解锁的情况下才能逃生。有m个开关。每个开关控制一些房间的门,但每个门恰好由两个开关控制。

您将获得门的初始配置。切换任何开关,即在其关闭时将其打开,或在打开时将其关闭,会切换该开关控制的门的状态。比如说,我们拨动开关 1,它连接到房间 1、2 和 3,分别为锁定、解锁和解锁。然后,切换开关后,它们会变为解锁、锁定和锁定。

你需要告诉Sherlock,是否存在同时解锁所有门的方法。

输入

输入的第一行包含两个整数 n 和 m (2 ≤ n ≤ 105, 2 ≤ m ≤ 105) - 房间数量和开关数量。

下一行包含 n 个空格分隔的整数 r1, r2, ..., rn (0 ≤ ri ≤ 1),它们告诉房间门的状态。如果 ri = 0,则第 i 个房间被锁定,否则被解锁。

接下来 m 行的第 i 行包含一个整数 xi (0 ≤ xi ≤ n),后跟由空格分隔的 xi 个不同整数,表示第 i 个开关控制的房间数量,后跟该开关控制的房间号。保证房间号在1到n的范围内。保证每扇门恰好由两个开关控制。

输出

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

示例

输入 #1

3 3
1 0 1
2 1 3
2 1 2
2 2 3

输出 #1

NO

输入 #2

3 3
1 0 1
3 1 2 3
1 2
2 1 3

输出 #2

YES

输入 #3

3 3
1 0 1
3 1 2 3
2 1 2
1 3

输出 #3

NO

注意

在第二个示例输入中,门的初始状态为 [1, 0, 1](0 表示锁定,1 — 解锁)。

切换开关 3 后,我们得到 [0, 0, 0],这意味着所有门都已锁定。

然后,切换开关 1 后,我们得到 [1, 1, 1],这意味着所有门都已解锁。

可以看出,对于第一个和第三个示例输入,不可能使所有门解锁。