P10441 [JOIST 2024] Table Tennis / Table Tennis

A table tennis tournament was held in the kingdom of JOI. $N$ beavers numbered from $1$ to $N$ participated in the tournament, and they played a round-robin tournament. You learned the following information about the match results from Bitaro. - There are no drawn matches. - There are exactly $M$ ways to choose $3$ beavers that form a “triple paradox”. Note that $3$ beavers $i, j, k$ ($1 \leq i < j < k \leq N$) form a “triple paradox” if and only if exactly one of the following two conditions holds. - - Beaver $i$ defeated beaver $j$, beaver $j$ defeated beaver $k$, and beaver $k$ defeated beaver $i$. - - Beaver $i$ defeated beaver $k$, beaver $k$ defeated beaver $j$, and beaver $j$ defeated beaver $i$. You are not sure whether the information provided by Bitaro is correct, so you decided to think about whether there are any match results consistent with Bitaro’s information. Write a program that, based on the information provided by Bitaro, determines whether there are any match results consistent with it; if there are, find any such match results.

One test case consists of $Q$ scenarios, numbered from $1$ to $Q$. Each scenario specifies the following values. - The number of beavers $N$ participating in the tournament. - The number of ways $M$ to choose $3$ beavers that form a “triple paradox”. The input format is as follows. - $Q$ For each scenario, the input format is as follows. - $N$ $M$

For each scenario, write the answer to standard output in the following order. In some scenarios, if there exist any match results consistent with the information, output in the following format. - Yes - $S_2$ - $S_3$ - ... - $S_N$ Here, for $S_i$ ($2 \leq i \leq N$), it is a string of length $i - 1$ consisting of characters '0' and '1'. The $j$-th character of $S_i$ is '0' if beaver $i$ was defeated by beaver $j$, and '1' if beaver $i$ defeated beaver $j$. If multiple results exist, you may output any one of them. In some scenarios, if there are no match results consistent with the information, output No.

#### Sample Explanation 1 There are $Q = 2$ scenarios. In this sample output, for scenario $1$, the result is: beaver $1$ defeated beaver $2$, beaver $2$ defeated beaver $3$, and beaver $3$ defeated beaver $1$. Therefore, beavers $1, 2, 3$ form a “triple paradox”. There is no other way to choose $3$ beavers, so there are exactly $1$ way to choose $3$ beavers that form a “triple paradox”. Another possible output for scenario $1$ is as follows. ``` Yes 1 01 ``` In scenario $2$, there are no match results consistent with the information. Therefore, output No. This sample input satisfies the constraints of subtasks $2,3,4,5,6$. #### Sample Explanation 2 In this sample output, for scenario $1$, the result is: beaver $1$ defeated beaver $4$, beaver $4$ defeated beaver $3$, and beaver $3$ defeated beaver $1$. Therefore, beavers $1,3,4$ form a “triple paradox”. There are two other ways to choose $3$ beavers that form a “triple paradox”: choosing beavers $2,3,4$ and choosing beavers $3,4,5$. Therefore, there are exactly $3$ ways to choose $3$ beavers that form a “triple paradox”. This sample input satisfies the constraints of all subtasks. ### Constraints - $1 \leq Q$. - $3 \leq N \leq 5000$. - $0 \leq M \leq \frac{1}{6} N(N - 1)(N - 2)$. - The sum of $N$ over the $Q$ scenarios does not exceed 5000. - All given values are integers. ### Subtasks 1. (5 points) $M \leq N - 2$. 2. (4 points) The sum of $N$ over the $Q$ scenarios does not exceed 7. 3. (23 points) The sum of $N$ over the $Q$ scenarios does not exceed 20. 4. (30 points) The sum of $N$ over the $Q$ scenarios does not exceed 150. 5. (15 points) The sum of $N$ over the $Q$ scenarios does not exceed 600. 6. (23 points) No additional constraints. Translated by ChatGPT 5