CF776D The Door Problem

Moriarty 把 $ n $ 个人分别困在酒店的 $ n $ 个不同房间里。一些房间的门是锁着的，另外一些是开着的。但是，有一个条件，只有当所有房间的门同时都是打开的时候，这些人才能逃脱。酒店里有 $ m $ 个开关。每个开关可以控制一些房间的门，但每扇门恰好被两个开关控制。 你得到了门的初始状态。每当你切换一个开关时（即打开变关闭，或关闭变打开），该开关所控制的所有房门的状态都会发生改变。例如，假设你切换了开关 $ 1 $，它连接的分别为房间 $ 1 $、$ 2 $ 和 $ 3 $，这些房间门当前分别为锁着、开着、开着。那么，切换后，这三扇门会分别变为：开着、锁着、锁着。 你需要告诉 Sherlock，是否存在一种切换开关的方式，使得所有门同时都被打开。

输入的第一行包含两个整数 $ n $ 和 $ m $（$ 2 \le n \le 10^{5} $，$ 2 \le m \le 10^{5} $），分别表示房间数和开关数。 第二行包含 $ n $ 个用空格分隔的整数 $ r_{1}, r_{2}, ..., r_{n} $（$ 0 \le r_{i} \le 1 $），表示每个房间门的当前状态。如果 $ r_{i}=0 $，则第 $ i $ 个房间门是锁着的；否则是开着的。 接下来的 $ m $ 行，第 $ i $ 行包含一个整数 $ x_{i} $（$ 0 \le x_{i} \le n $），接着是 $ x_{i} $ 个不重复的整数，分别表示第 $ i $ 个开关控制的房间数量以及各个被控制的房间编号。保证房间编号范围在 $ 1 $ 到 $ n $ 之间。保证每扇门恰好被两个不同的开关控制。

如果存在一种切换开关的方式可以同时打开所有房门，则输出 "YES"（不含引号），否则输出 "NO"。

在第二个输入样例中，各房门初始状态为 $ [1,0,1] $（$ 0 $ 表示锁着，$ 1 $ 表示开着）。 第一次切换第 $ 3 $ 个开关后，状态变为 $ [0,0,0] $，表示所有门都被锁住了。 然后再切换第 $ 1 $ 个开关，状态变为 $ [1,1,1] $，即所有房门都打开。 可以发现，对于第一个和第三个样例输入，都不存在使所有门都打开的切换方式。 由 ChatGPT 5 翻译