P7876 "SWTR-7" Scores (hard version)

#### This problem is the hard version of Scores. Note that the constraints are different from the [easy](https://www.luogu.com.cn/problem/P7873) version. #### Please pay attention to the special time and memory limits.

There are $n$ students in Xiao A's class. Recently, they took an exam with $m$ subjects. The score of student $i$ in subject $j$ is an **integer** $s_{i,j}\ (0\leq s_{i,j}\leq 100)$. Students care a lot about their rank in the class, so they often compare their scores with others. If a student $i$ has a higher score than $j$ in **at least one subject**, then they feel that they are not worse than $j$. On the other hand, if they have a lower score than $j$ in **every subject**, then they feel they are completely crushed by $j$. In fact, **the two situations above are not strictly opposite**. However, Xiao A, who loves gossip, learned the score relationship between every pair of students, and he was surprised to find that: **a student $i$ is either crushed by $j$, or not worse than $j$.** At the same time, **if $i$ and $j$ are both crushed by the same person, or they both crush the same person, then between $i$ and $j$ one of them is crushed by the other.** We use a matrix $a_{i,j}\ (i\neq j)$ to describe the relationships Xiao A knows: $a_{i,j}=0$ means $i$ is crushed by $j$; $a_{i,j}=1$ means $i$ is not worse than $j$. Xiao A wants to know whether such a situation can actually happen, i.e. whether there exists an $n\times m$ score table $s$ that satisfies the score relationships described by matrix $a$, so as to determine whether someone lied. If such an $s$ exists, first output $\texttt{YES}$, then output **any** valid score table that meets the requirements. Otherwise, output $\texttt{NO}$. Note: the required conditions on $s$ are exactly the constraints given by $a$, **not only** the properties Xiao A discovered, because **those discovered properties are already reflected in the given $a$**.

**This problem contains multiple test cases.** The first line contains an integer $t$, **which indicates the test point ID**. The second line contains an integer $T$, **which indicates the number of test cases**. For each test case: The first line contains two integers $n,m$. Then follow $n$ lines, each containing $n$ space-separated 0 or 1 values describing $a$. The $j$-th number in line $i+1$ represents $a_{i,j}$. In particular, to make input easier, **it is defined that $a_{i,i}=0$**. But you should know that **it has no actual meaning**.

For each test case: If there is no $s$ that satisfies the conditions, output one line with the string $\texttt{NO}$. Otherwise, first output one line with the string $\texttt{YES}$, then output $n$ lines, each containing $m$ space-separated integers. The $j$-th number in line $i+1$ represents $s_{i,j}\ (0\leq s_{i,j}\leq 100)$.

**"Special Judge"** **This problem uses Special Judge. Please read the output format carefully. Incorrect output format may lead to UKE or WA.** The SPJ will first check whether your first line matches the correct answer. If it matches and the answer is $\texttt{YES}$, then the SPJ will check whether your output satisfies all constraints. If a solution exists and you output $\texttt{YES}$ but your construction is wrong, you will get $50\%$ of the score for that test point. The constraints you must satisfy are: - $0\leq s_{i,j}\leq 100$. - For any $i,j\ (i\neq j)$, if $a_{i,j}=0$, then for any $k\ (1\leq k\leq m)$, $s_{i,k}s_{j,k}$. You should note that all outputs must strictly follow the output format. If you correctly determine whether a solution exists, but in your output construction $s_{i,j}100$, the SPJ will judge it as WA and you will get $0$ points, not $50\%\ \times$ the test point score. **"Constraints and Conventions"** This problem has 6 test points. - Testcase #0 (1 point): the sample. - Testcase #1 (10 points): $n=1$. - Testcase #2 (10 points): $m=1$. - Testcase #3 (30 points): $m=2$. - Testcase #4 (20 points): $a_{i,j}=1\ (i\neq j)$. - Testcase #5 (29 points): no special constraints. For $100\%$ of the data, $1\leq n,m\leq 100$, $a_{i,j}\in\{0,1\}$, $T=50$ (except Testcase #0). For the constraints on $a$: if $a_{i,j}=a_{i,k}=0$, then at least one of $a_{j,k}$ and $a_{k,j}$ is $0$; if $a_{i,k}=a_{j,k}=0$, then at least one of $a_{i,j}$ and $a_{j,i}$ is $0$. For all test points, **time limit is 500 ms, memory limit is 16 MB.** **"Source"** [Sweet Round 07](https://www.luogu.com.cn/contest/51773) A2. idea & solution & data: [Alex_Wei](https://www.luogu.com.cn/user/123294); verification: [chenxia25](https://www.luogu.com.cn/user/138400). Translated by ChatGPT 5