Description

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$.

Input Format

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.

Output Format

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)$.

0
5
5 3
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
2 7
0 1
0 0
5 4
0 1 1 0 1
0 0 0 0 1
0 1 0 0 1
1 1 1 0 1
1 1 1 1 0
3 1
0 1 1
1 0 1
1 1 0
3 2
0 1 0
0 0 1
1 0 0

YES
100 99 97
98 100 99
95 97 100
0 98 100
99 99 99
YES
98 100 94 98 72 53 53
97 99 93 97 71 52 52
YES
90 80 70 60
50 40 30 20
60 50 40 30
100 90 80 70
40 60 80 100
NO
NO

Hint

"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}$; if $a_{i,j}=1$, then there exists a $k\in [1,m]$ such that $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}<0$ or $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 A2.
idea & solution & data: Alex_Wei; verification: chenxia25.

Translated by ChatGPT 5