B. Mystical Mosaic

有一个由 #cf_span[n] 行、每行 #cf_span[m] 个初始为白色的单元格组成的矩形网格。 Arkady 对该网格执行了若干次（可能为零次）操作。在第 #cf_span[i] 次操作中，选择一个非空的行子集 #cf_span[Ri] 和一个非空的列子集 #cf_span[Ci]。对于每个属于 #cf_span[Ri] 的行 #cf_span[r] 和每个属于 #cf_span[Ci] 的列 #cf_span[c]，行 #cf_span[r] 与列 #cf_span[c] 的交点被染成黑色。 还有一个约束条件：在所有操作中，每一行或每一列最多只能被选择一次。换句话说，不存在任意一对 #cf_span[(i, j)]（#cf_span[i < j]），使得 #cf_span[Ri \\cap Rj \\neq \\varnothing] 或 #cf_span[Ci \\cap Cj \\neq \\varnothing]，其中 #cf_span[\\cap] 表示集合的交集，#cf_span[\\varnothing] 表示空集。 你需要判断是否存在一个合法的操作序列，能够生成给定的最终网格。 第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m] #cf_span[(1 ≤ n, m ≤ 50)] —— 分别表示网格的行数和列数。 接下来的 #cf_span[n] 行，每行包含一个长度为 #cf_span[m] 的字符串，每个字符要么是 '_._'（表示白色单元格），要么是 '_#_'（表示黑色单元格），代表目标布局。 如果给定的网格可以通过某个合法的操作序列实现，则输出 "_Yes_"；否则输出 "_No_"（均不带引号）。 你可以以任意大小写形式输出每个字符。 对于第一个示例，目标布局可以通过 #cf_span[3] 次操作实现，如下所示。 对于第二个示例，目标布局无法实现，因为为了染黑中心行，必须在一次操作中选择第三行和所有列，但此后任何列都无法再被选择，因此无法再染黑中心列中的其他单元格。 ## Input 第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m] #cf_span[(1 ≤ n, m ≤ 50)] —— 分别表示网格的行数和列数。接下来的 #cf_span[n] 行，每行包含一个长度为 #cf_span[m] 的字符串，每个字符要么是 '_._'（表示白色单元格），要么是 '_#_'（表示黑色单元格），代表目标布局。 ## Output 如果给定的网格可以通过某个合法的操作序列实现，则输出 "_Yes_"；否则输出 "_No_"（均不带引号）。你可以以任意大小写形式输出每个字符。 [samples] ## Note 对于第一个示例，目标布局可以通过 #cf_span[3] 次操作实现，如下所示。对于第二个示例，目标布局无法实现，因为为了染黑中心行，必须在一次操作中选择第三行和所有列，但此后任何列都无法再被选择，因此无法再染黑中心列中的其他单元格。

Let $ G \in \{0,1\}^{n \times m} $ be the given grid, where $ G_{r,c} = 1 $ if cell $ (r,c) $ is black, and $ 0 $ if white. Let $ \mathcal{R} = \{R_1, R_2, \dots, R_k\} $ be a collection of non-empty subsets of rows $ \{1, 2, \dots, n\} $, and $ \mathcal{C} = \{C_1, C_2, \dots, C_k\} $ be a collection of non-empty subsets of columns $ \{1, 2, \dots, m\} $, for some $ k \geq 0 $, such that: - For all $ i \neq j $, $ R_i \cap R_j = \emptyset $ and $ C_i \cap C_j = \emptyset $ (each row and each column is used in at most one operation). The grid $ G $ is produced if and only if: $$ G_{r,c} = 1 \iff \exists\, i \text{ such that } r \in R_i \text{ and } c \in C_i. $$ **Objective:** Determine whether such collections $ \mathcal{R}, \mathcal{C} $ exist. --- **Equivalent characterization:** Define: - $ \mathcal{R}^* = \{ r \in [n] \mid \exists c \in [m], G_{r,c} = 1 \} $ — rows with at least one black cell. - $ \mathcal{C}^* = \{ c \in [m] \mid \exists r \in [n], G_{r,c} = 1 \} $ — columns with at least one black cell. For each row $ r \in \mathcal{R}^* $, define its *pattern*: $ P_r = \{ c \in [m] \mid G_{r,c} = 1 \} $. For each column $ c \in \mathcal{C}^* $, define its *pattern*: $ Q_c = \{ r \in [n] \mid G_{r,c} = 1 \} $. **Necessary and sufficient condition:** There exists a partition of $ \mathcal{R}^* $ into disjoint non-empty subsets $ R_1, \dots, R_k $, and a partition of $ \mathcal{C}^* $ into disjoint non-empty subsets $ C_1, \dots, C_k $, such that for all $ i \in [k] $: $$ \forall r \in R_i,\ \forall c \in C_i,\ G_{r,c} = 1, $$ and $$ \forall r \in R_i,\ P_r = C_i, \quad \forall c \in C_i,\ Q_c = R_i. $$ In other words: All rows in a group $ R_i $ must have *identical* black patterns, equal to $ C_i $, and all columns in a group $ C_i $ must have *identical* black patterns, equal to $ R_i $. Equivalently, define an equivalence relation on rows: $ r \sim r' \iff P_r = P_{r'} $, and on columns: $ c \sim c' \iff Q_c = Q_{c'} $. Then, the grid is realizable if and only if: - The set of distinct row patterns $ \{P_r \mid r \in \mathcal{R}^*\} $ is in bijection with the set of distinct column patterns $ \{Q_c \mid c \in \mathcal{C}^*\} $, - And for each distinct row pattern $ P $, the set of rows with pattern $ P $ is exactly the set of columns whose pattern is the corresponding column pattern $ Q $, and vice versa. More precisely: Let $ \mathcal{P} = \{ P_1, P_2, \dots, P_k \} $ be the distinct row patterns. Let $ \mathcal{Q} = \{ Q_1, Q_2, \dots, Q_k \} $ be the distinct column patterns. Then, there exists a bijection $ f: \mathcal{P} \to \mathcal{Q} $ such that: - For every row $ r $ with pattern $ P_i $, the set of columns where it is black is $ P_i $, - For every column $ c $ with pattern $ Q_j $, the set of rows where it is black is $ Q_j $, - And $ f(P_i) = Q_j \iff P_i = Q_j $ as sets? Not exactly. Wait — better: Let $ S_i \subseteq \mathcal{R}^* $ be the set of rows with pattern $ P_i $. Let $ T_j \subseteq \mathcal{C}^* $ be the set of columns with pattern $ Q_j $. Then, the grid is realizable **iff**: - The number of distinct row patterns equals the number of distinct column patterns: $ |\mathcal{P}| = |\mathcal{Q}| = k $, - And there exists a bijection $ \sigma: \{1,\dots,k\} \to \{1,\dots,k\} $ such that for all $ i $: $$ \bigcup_{r \in S_i} P_r = T_{\sigma(i)}, \quad \text{and} \quad \bigcup_{c \in T_{\sigma(i)}} Q_c = S_i. $$ But since all rows in $ S_i $ have the same pattern $ P_i $, we have $ \bigcup_{r \in S_i} P_r = P_i $. Similarly, $ \bigcup_{c \in T_j} Q_c = Q_j $. So the condition simplifies to: > There exists a bijection $ \sigma: \mathcal{P} \to \mathcal{Q} $ such that for each row pattern $ P \in \mathcal{P} $, > $$ > \sigma(P) = \{ c \in [m] \mid \exists r \text{ with } P_r = P \text{ and } G_{r,c} = 1 \} = P, > $$ > and for each column pattern $ Q \in \mathcal{Q} $, > $$ > \sigma^{-1}(Q) = \{ r \in [n] \mid \exists c \text{ with } Q_c = Q \text{ and } G_{r,c} = 1 \} = Q. > $$ Wait — this implies $ P = \sigma(P) $, so $ \mathcal{P} = \mathcal{Q} $ as sets of sets. Actually, we must have: For each row pattern $ P $, the set of columns where *any* row with pattern $ P $ is black is exactly $ P $. But those columns must form a single group $ C_i $, and their column patterns must all be equal to the set of rows with pattern $ P $, i.e., $ Q_c = \{ r \mid P_r = P \} $ for all $ c \in P $. So: Let $ S_P = \{ r \in [n] \mid P_r = P \} $ — the set of rows with pattern $ P $. Let $ T_P = P $ — the set of columns where those rows are black. Then, for each column $ c \in T_P $, we must have $ Q_c = S_P $. Therefore, the condition is: > For every distinct row pattern $ P $, > the set of columns $ c $ with $ G_{r,c} = 1 $ for some (hence all) $ r \in S_P $ is exactly $ P $, > and for every column $ c \in P $, its pattern $ Q_c $ is exactly $ S_P $. Thus, the grid is realizable **iff**: - For every row $ r $, define $ P_r = \{ c \mid G_{r,c} = 1 \} $, - For every column $ c $, define $ Q_c = \{ r \mid G_{r,c} = 1 \} $, - Then, for any two rows $ r_1, r_2 $: $$ P_{r_1} = P_{r_2} \iff Q_c = Q_{c'} \text{ for all } c \in P_{r_1}, c' \in P_{r_2}, $$ and $$ \text{if } P_{r_1} = P_{r_2}, \text{ then } \forall c \in P_{r_1},\ Q_c = \{ r \mid P_r = P_{r_1} \}. $$ In other words: **Final formal condition:** Let $ \mathcal{P} = \{ P_r \mid r \in [n], P_r \neq \emptyset \} $, and for each $ P \in \mathcal{P} $, define $ S_P = \{ r \in [n] \mid P_r = P \} $. Then, for every $ P \in \mathcal{P} $ and every $ c \in P $, it must hold that: $$ Q_c = S_P. $$ Additionally, every column $ c $ with $ G_{r,c} = 1 $ for some $ r $ must satisfy $ Q_c \in \{ S_P \mid P \in \mathcal{P} \} $, and every such $ S_P $ must be equal to $ Q_c $ for some $ c \in P $. Thus, the grid is realizable **if and only if**: $$ \boxed{ \forall c \in [m],\ \exists P \in \mathcal{P} \text{ such that } c \in P \text{ and } Q_c = S_P } $$ And since $ P = \{ c \mid G_{r,c} = 1 \} $ for any $ r \in S_P $, this is well-defined. **Algorithmic check:** 1. For each row $ r $, compute $ P_r = \{ c \mid G_{r,c} = 1 \} $. 2. For each column $ c $, compute $ Q_c = \{ r \mid G_{r,c} = 1 \} $. 3. Let $ \mathcal{P} = \{ P_r \mid P_r \neq \emptyset \} $. 4. For each distinct non-empty pattern $ P \in \mathcal{P} $: - Let $ S_P = \{ r \mid P_r = P \} $. - For every column $ c \in P $, check that $ Q_c = S_P $. 5. Also, ensure that every column $ c $ with $ Q_c \neq \emptyset $ appears in some $ P \in \mathcal{P} $ (i.e., $ \exists r $ such that $ G_{r,c} = 1 $), which is already implied. 6. If all such checks pass, output "Yes"; else, "No". This is the formal characterization.