English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
Output "_YES_" without quotes, if it is possible to open all doors at the same time, otherwise output "_NO_" without quotes.
[samples]
## Note
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.
莫里亚蒂将 #cf_span[n] 个人困在酒店的 #cf_span[n] 个不同房间中。有些房间上锁，有些未上锁。但有一个条件：只有当所有门同时解锁时，酒店中的人才能逃脱。共有 #cf_span[m] 个开关。每个开关控制某些房间的门，但每扇门恰好由 *两个* 开关控制。
你将获得门的初始状态。切换任意一个开关（即当开关处于关闭状态时将其打开，或当处于打开状态时将其关闭）会切换该开关所控制的门的状态。例如，我们切换了开关 #cf_span[1]，它连接了房间 #cf_span[1]、#cf_span[2] 和 #cf_span[3]，这三个房间的状态分别为上锁、未上锁和未上锁。切换后，它们的状态变为未上锁、上锁和上锁。
你需要告诉夏洛克，是否存在一种方法，使得所有门同时解锁。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 105]，#cf_span[2 ≤ m ≤ 105]）——分别表示房间数和开关数。
接下来一行包含 #cf_span[n] 个空格分隔的整数 #cf_span[r1, r2, ..., rn]（#cf_span[0 ≤ ri ≤ 1]），表示房间门的状态。若 #cf_span[ri = 0]，则第 #cf_span[i] 个房间上锁；否则未上锁。
接下来的 #cf_span[m] 行中，第 #cf_span[i] 行包含一个整数 #cf_span[xi]（#cf_span[0 ≤ xi ≤ n]），后跟 #cf_span[xi] 个用空格分隔的互异整数，表示第 #cf_span[i] 个开关控制的房间数量及其控制的房间编号。房间编号保证在 #cf_span[1] 到 #cf_span[n] 范围内，且每扇门恰好由两个开关控制。
如果存在一种方法使所有门同时解锁，请输出 "_YES_"（不含引号）；否则输出 "_NO_"（不含引号）。
在第二个示例输入中，门的初始状态为 #cf_span[[1, 0, 1]]（#cf_span[0] 表示上锁，#cf_span[1] 表示未上锁）。
切换开关 #cf_span[3] 后，状态变为 #cf_span[[0, 0, 0]]，表示所有门均上锁。
再切换开关 #cf_span[1] 后，状态变为 #cf_span[[1, 1, 1]]，表示所有门均解锁。
可以观察到，对于第一个和第三个示例输入，无法使所有门解锁。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 105]，#cf_span[2 ≤ m ≤ 105]）——分别表示房间数和开关数。接下来一行包含 #cf_span[n] 个空格分隔的整数 #cf_span[r1, r2, ..., rn]（#cf_span[0 ≤ ri ≤ 1]），表示房间门的状态。若 #cf_span[ri = 0]，则第 #cf_span[i] 个房间上锁；否则未上锁。第 #cf_span[i] 行接下来的 #cf_span[m] 行中，每行包含一个整数 #cf_span[xi]（#cf_span[0 ≤ xi ≤ n]），后跟 #cf_span[xi] 个用空格分隔的互异整数，表示第 #cf_span[i] 个开关控制的房间数量及其控制的房间编号。房间编号保证在 #cf_span[1] 到 #cf_span[n] 范围内，且每扇门恰好由两个开关控制。
## Output
如果存在一种方法使所有门同时解锁，请输出 "_YES_"（不含引号）；否则输出 "_NO_"（不含引号）。
[samples]
## Note
在第二个示例输入中，门的初始状态为 #cf_span[[1, 0, 1]]（#cf_span[0] 表示上锁，#cf_span[1] 表示未上锁）。切换开关 #cf_span[3] 后，状态变为 #cf_span[[0, 0, 0]]，表示所有门均上锁。再切换开关 #cf_span[1] 后，状态变为 #cf_span[[1, 1, 1]]，表示所有门均解锁。可以观察到，对于第一个和第三个示例输入，无法使所有门解锁。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of rooms and switches, respectively.
Let $ r = (r_1, r_2, \dots, r_n) \in \{0,1\}^n $ be the initial state of the doors, where $ r_i = 0 $ means locked and $ r_i = 1 $ means unlocked.
Let $ S = (S_1, S_2, \dots, S_m) $ be the set of switches, where each switch $ S_j $ controls a subset of rooms $ R_j \subseteq \{1, 2, \dots, n\} $.
Each room $ i $ is controlled by exactly two switches, i.e., $ |\{ j \mid i \in R_j \}| = 2 $ for all $ i \in \{1, \dots, n\} $.
Let $ x = (x_1, x_2, \dots, x_m) \in \{0,1\}^m $ be the toggle vector, where $ x_j = 1 $ means switch $ j $ is toggled, and $ x_j = 0 $ means it is not.
**Constraints**
1. $ 2 \le n \le 10^5 $
2. $ 2 \le m \le 10^5 $
3. $ r_i \in \{0,1\} $ for all $ i \in \{1, \dots, n\} $
4. For each switch $ j $, $ |R_j| \ge 0 $, and all room indices in $ R_j $ are distinct and in $ \{1, \dots, n\} $
5. Each room $ i $ is controlled by exactly two switches: $ \exists! \, j_1 \ne j_2 $ such that $ i \in R_{j_1} \cap R_{j_2} $
**Objective**
Determine whether there exists a toggle vector $ x \in \{0,1\}^m $ such that for every room $ i \in \{1, \dots, n\} $:
$$
r_i \oplus x_{j_1} \oplus x_{j_2} = 1
$$
where $ j_1, j_2 $ are the two switches controlling room $ i $, and $ \oplus $ denotes XOR.
Equivalently, for each room $ i $ controlled by switches $ j_1 $ and $ j_2 $:
$$
x_{j_1} \oplus x_{j_2} = 1 \oplus r_i
$$
This defines a system of $ n $ XOR equations over $ \mathbb{F}_2 $ on $ m $ variables.
Output "YES" if the system is satisfiable, otherwise "NO".
API Response (JSON)
{
"problem": {
"name": "D. The Door Problem",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF776D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "莫里亚蒂将 #cf_span[n] 个人困在酒店的 #cf_span[n] 个不同房间中。有些房间上锁，有些未上锁。但有一个条件：只有当所有门同时解锁时，酒店中的人才能逃脱。共有 #cf_span[m] 个开关。每个开关控制某些房间的门，但每扇门恰好由 *两个* 开关控制。\n\n你将获得门的初始状态。切换任意一个开关（即当开关处于关闭状态时将其打开，或当处于打开状态时将其关闭）会切换该开关所控制的门...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of rooms and switches, respectively. \nLet $ r = (r_1, r_2, \\dots, r_n) \\in \\{0,1\\}^n $ be the initial state of the doors, where $ r_i...",
"is_translate": false,
"language": "Formal"
}
]
}