2024-sp_Table_Tennis — JOI JOI_spring
Task type: batch | Time limit: 1 s | Memory limit: 1024 MB | Difficulty: 21
Algorithms: graph theory, constructive, combinatorics, recursion

{
    "type": "formatting",
    "description": "Added missing heading levels to 'Input', 'Output', 'Constraints', 'Subtasks', and 'Sample Input and Output'."
  },
  {
    "type": "formatting",
    "description": "Fixed spacing and indentation issues for better readability."
  },
  {
    "type": "formatting",
    "description": "Corrected the broken Markdown list for the trilemma conditions. Changed hyphens to bullets."
  },
  {
    "type": "formatting",
    "description": "Replaced unicode ellipses with standard '...'."
  },
  {
    "type": "formatting",
    "description": "Fixed the mathematical notation in the Constraints section using LaTeX syntax."
  },
  {
    "type": "content",
    "description": "Corrected minor typos."
  }
]
```
\`\`\`markdown
![](_page_0_Picture_0.jpeg)

## Table Tennis

A table tennis competition was held in JOI Kingdom. *N* beavers numbered from 1 to *N* participated in this competition, and a round-robin tournament was conducted.

You were told the following information about the result of this competition from Bitaro.

- There were no draw match.
- There are exactly *M* ways to choose 3 beavers which are trilemma. Note that 3 beavers *i*, *j*, *k* (1 ≤ *i* < *j* < *k* ≤ *N*) are trilemma if and only if exactly one of the following 2 conditions is satisfied.
    - Beaver *i* beat beaver *j*, beaver *j* beat beaver *k*, and beaver *k* beat beaver *i*.
    - Beaver *i* beat beaver *k*, beaver *k* beat beaver *j*, and beaver *j* beat beaver *i*.

You don't know whether the information from Bitaro is correct, so you decided to think whether there are any results of this competition which accord with the information from Bitaro.

Write a program which, given the information from Bitaro, judge whether there are any results of this competition which accord with the information, and if so, finds one such result of this competition.

![](_page_1_Picture_0.jpeg)

### Input

A test case consists of *Q* scenarios, numbered from 1 to *Q*. The following values are specified for each scenario.

- The number of beavers *N* which participated in the competition.
- The number of ways *M* to choose 3 beavers which are trilemma.

The format of the input data is as follows:

```
Q
(Input for Scenario 1)
(Input for Scenario 2)
...
(Input for Scenario Q)
```

The format of the input data for each scenario is as follows:

```
N M
```

### Output

Write to standard output the answer of Scenario 1, 2, ..., *Q* in order as follows.

In some scenario, if there are any results of this competition which accord with the information, output as follows:

```
Yes
S2
S3
...
SN
```

Here, *Si* (2 ≤ *i* ≤ *N*) is a string of which characters are '0' or '1' and length is *i* - 1. The *j*-th character of *Si* is '0' means beaver *i* was defeated by beaver *j*, and the *j*-th character of *Si* is '1' means beaver *i* won against beaver *j*. If multiple results exist, you can output any of them.

In some scenario, if there are not any results of this competition which accord with the information, output `No`.

![](_page_2_Picture_0.jpeg)

### Constraints

- 1 ≤ *Q*.
- 3 ≤ *N* ≤ 5000.
- 0 ≤ *M* ≤ $\frac{1}{6}N(N - 1)(N - 2)$.
- The sum of *N* for the *Q* scenarios is less than or equal to 5000.
- Given values are all integers.

### Subtasks

1. (5 points) *M* ≤ *N* − 2.
2. (4 points) The sum of *N* for the *Q* scenarios is less than or equal to 7.
3. (23 points) The sum of *N* for the *Q* scenarios is less than or equal to 20.
4. (30 points) The sum of *N* for the *Q* scenarios is less than or equal to 150.
5. (15 points) The sum of *N* for the *Q* scenarios is less than or equal to 600.
6. (23 points) No additional constraints.

![](_page_3_Picture_0.jpeg)

### Sample Input and Output

| Sample Input 1 | Sample Output 1 |
|----------------|-----------------|
| 2              | Yes             |
| 3 1            | 0               |
| 4 4            | 10              |
|                | No              |

There are *Q* = 2 scenarios.

In the results of scenario 1 in this sample output, beaver 1 won beaver 2, beaver 2 won beaver 3, and beaver 3 won beaver 1. Therefore, 3 beavers 1, 2, 3 are trilemma. There is no other ways to choose 3 beavers, so there are exactly 1 ways to choose 3 beavers which are trilemma.

There is another output corresponds to scenario 1 as follows:

```
Yes
1
01

Starter code: