P13007 T622835 【MX-X13-T2】"KDOI-12" Don't Think About the Future, Leave It to Your Future Self

Your future self is participating in a mock contest.

The mock contest consists of $T$ problems. Each problem has $n$ subtasks and $m$ special properties. Each subtask satisfies a subset of the $m$ special properties. A **subtask dependency** $(i,j)$ means that subtask $j$ depends on subtask $i$—that is, subtask $j$ can only be passed after subtask $i$ is passed. Considering that the problem setters are lazy and the online judge is "not very smart," the number of subtask dependencies should be minimized. Now, you need to determine the minimum number of subtask dependencies required to ensure: 1. There does **not** exist a pair of subtasks $(x, y)$ such that: - All test cases satisfying subtask $y$ must also satisfy subtask $x$, but - It is still **possible** to pass subtask $y$ **without** passing subtask $x$. 2. There does **not** exist a pair of subtasks $(x, y)$ such that: - There exists a test case satisfying subtask $y$ but **not** satisfying subtask $x$, but - It is **impossible** to pass subtask $y$ **without** passing subtask $x$. Formally, let $S_i$ denote the set of special properties satisfied by subtask $i$. You need to select the smallest possible number of $(u_x, v_x)$ pairs such that: - For any $(i,j)$ where $S_i \subseteq S_j$, there exists a sequence $j = p_1, p_2, \dots, p_m = i$ such that for all $1 \leq k < m$, there exists $x$ where $(u_x, v_x) = (p_k, p_{k+1})$. - For any $(i,j)$ where $S_i \not\subseteq S_j$, there does **not** exist any sequence $j = p_1, p_2, \dots, p_m = i$ such that for all $1 \leq k < m$, there exists $x$ where $(u_x, v_x) = (p_k, p_{k+1})$. Your task is to find the minimum number of such pairs.

- The first line contains a positive integer $T$, the number of problems. - For each problem: - The first line contains two positive integers $n$ and $m$, the number of subtasks and special properties, respectively. - The next $n$ lines each contain a binary string of length $m$. The $j$-th character of the $i$-th string is `1` if and only if the $i$-th subtask satisfies the $j$-th special property. - **It is guaranteed that no two subtasks satisfy the exact same set of special properties.**

For each problem, output a single non-negative integer—the minimum number of subtask dependencies required.

### **Sample Explanation** For the second problem: Suppose the four special properties are $\text{ABCD}$. Then, the five subtasks correspond to the following sets: - $\{\text{A}, \text{B}, \text{C}\}$ - $\{\text{A}, \text{B}\}$ - $\{\text{A}\}$ - $\{\text{D}\}$ - $\varnothing$ (empty set) The following dependency configuration is optimal: - $(1, 2)$ - $(2, 3)$ - $(3, 5)$ - $(4, 5)$ ### **Data Range** | Test Case | $n, m \leq$ | Special Property | |:--:|:--:|:--:| | $1\sim2$ | $2$ | None | | $3\sim9$ | $5$ | None | | $10\sim13$ | $10$ | None | | $14\sim20$ | $16$ | A | | $21\sim25$ | $16$ | None | - **Special Property A**: Each subtask satisfies at most two special properties. For all test cases: - $1 \leq T \leq 6$, - $1 \leq n, m \leq 16$, - Input strings consist of `0` and `1`, - No two subtasks share the exact same set of special properties. --- *Translated by DeepSeek V3.*