The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 4 – Table Tennis

Table Tennis
A table tennis competition was held in JOI Kingdom. N beavers numbered from 1 to N participated in thiscompetition, 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 satisﬁed.
◦ 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, ﬁnds one such result of this competition.

Table Tennis– 1 / 4

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 4 – Table Tennis

Input
A test case consists of Q scenarios, numbered from 1 to Q. The following values are speciﬁed for eachscenario.
• 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.
NMOutput
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 asfollows.
Yes
S2S3..
.
SNHere, S i (2 ≦ i ≦ N) is a string of which characters are ‘0’ or ‘1’ and length is i − 1. j-th character of S i is ‘0’means beaver i was defeated beaver j, and j-th character of S i is ‘1’ means beaver i won 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.

Table Tennis– 2 / 4

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 4 – Table Tennis

Constraints• 1 ≤ Q．
• 3 ≤ N ≤ 5 000．
1
• 0 ≤ M ≤ N(N − 1)(N − 2)．
6• The sum of N for the Q scenarios is less than or equal to 5 000.
• 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.

Table Tennis– 3 / 4

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 4 – Table Tennis

Sample Input and Output
Sample Input 1Sample Output 12Yes3 104 410NoThere 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
101
In scenario 2, there are not any results of this competition which accord with the information. Therefore,output No.
This sample input satisﬁes the constraints of Subtasks 2, 3, 4, 5, 6.
Sample Input 2

Sample Output 2

1Yes

5 3011001
0101

In the results of scenario 1 in this sample output, beaver 1 won beaver 4, beaver 4 won beaver 3, and beaver
3 won beaver 1. Therefore, 3 beavers 1, 3, 4 are trilemma. There are two other ways to choose 3 beavers which
are trilemma: choose beavers 2, 3, 4 and choose beavers 3, 4, 5. Therefore, there are exactly 3 ways to choose 3
beavers which are trilemma.
This sample input satisﬁes the constraints of all the subtasks.

Table Tennis– 4 / 4