L - 卓球 (Table Tennis) Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

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 matches.
  • There are exactly M ways to choose 3 beavers which are trilemma. Note that 3 beavers i, j, k (1 \le i < j < k \le 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, judges whether there are any results of this competition which accord with the information, and if so, finds one such result of this competition.


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)
\vdots
(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, \ldots, 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
S_2
S_3
\vdots
S_N

Here, S_i (2 \le i \le N) is a string of which characters are 0 or 1 and length is i - 1. The j-th character of S_i (1 \le j \le i - 1) being 0 means beaver i was defeated by beaver j, and the j-th character of S_i being 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.


Constraints

  • 1 \le Q.
  • 3 \le N \le 5\,000.
  • 0 \le M \le \dfrac{1}{6}N(N - 1)(N - 2).
  • 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 \le 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.

Sample Input 1

2
3 1
4 4

Sample Output 1

Yes
0
10
No

There are Q = 2 scenarios.

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

There is another output corresponding to scenario 1 as follows.

Yes
1
01

In scenario 2, there are not any results of this competition which accord with the information. Therefore, output No.

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6.


Sample Input 2

1
5 3

Sample Output 2

Yes
0
11
001
0101

In the results of scenario 1 in this sample output, beaver 1 won against beaver 4, beaver 4 won against beaver 3, and beaver 3 won against 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 satisfies the constraints of all the subtasks.

配点 : 100 点

問題文

JOI 国で卓球の大会が行われた.大会には 1 から N までの番号が付けられている N 匹のビーバーが出場し,総当たりのリーグ戦が行われた.

あなたはビ太郎から大会の試合結果について以下の情報を聞いた.

  • どの試合も引き分けではなかった.
  • 三すくみとなるような 3 匹のビーバーの選び方はちょうど M 通りであった.ただし,3 匹のビーバー i, j, k (1 \leqq i < j < k \leqq N) が三すくみであるとは,以下の 2 つの条件のうちちょうど 1 つが成り立つことをいう.
    • ビーバー i がビーバー j に勝利し,ビーバー j がビーバー k に勝利し,ビーバー k がビーバー i に勝利した.
    • ビーバー i がビーバー k に勝利し,ビーバー k がビーバー j に勝利し,ビーバー j がビーバー i に勝利した.

あなたはビ太郎から聞いた情報が正確か分からないため,聞いた情報に合致するような大会の試合結果が存在するか考えることにした.

ビ太郎から聞いた情報が与えられたとき,情報に合致する試合結果が存在するか判定し,もし存在するならばそのような試合結果を 1 つ求めるプログラムを作成せよ.


入力

1 つのテストケースは Q 個のシナリオからなり,シナリオには 1 から Q までの番号が付けられている.各シナリオに対して,以下の値が定められている.

  • 大会に参加したビーバーの数 N.
  • 三すくみとなるような 3 匹のビーバーの選び方 M.

ここで,入力は以下の形式で標準入力から与えられる.

Q
(シナリオ 1 に対する入力)
(シナリオ 2 に対する入力)
\vdots
(シナリオ Q に対する入力)

また,それぞれのシナリオに対する入力は,以下の形式で与えられる.

N M

出力

標準出力に,シナリオ 1, 2, \ldots, Q の順に以下の形式で出力せよ.

あるシナリオについて,情報に合致する試合結果が存在する場合,以下の形式で出力せよ.

Yes
S_2
S_3
\vdots
S_N

ここで,S_i (2 \leqq i \leqq N) は 0 または 1 からなる i - 1 文字の文字列である.S_i の j 文字目 (1 \leqq j \leqq i - 1) が 0 のときビーバー i がビーバー j に敗北したことを,1 のときビーバー i がビーバー j に勝利したことを示す.情報に合致する試合結果が複数存在する場合は,そのうちどれを出力してもよい.

あるシナリオについて,情報に合致する試合結果が存在しない場合,No と出力せよ.


制約

  • 1 \leqq Q.
  • 3 \leqq N \leqq 5\,000.
  • 0 \leqq M \leqq \dfrac{1}{6}N(N - 1)(N - 2).
  • Q 個のシナリオにおける N の値の合計は 5\,000 以下である.
  • 入力される値はすべて整数である.

小課題

  1. (5 点) M \leqq N - 2.
  2. (4 点) Q 個のシナリオにおける N の値の合計は 7 以下である.
  3. (23 点) Q 個のシナリオにおける N の値の合計は 20 以下である.
  4. (30 点) Q 個のシナリオにおける N の値の合計は 150 以下である.
  5. (15 点) Q 個のシナリオにおける N の値の合計は 600 以下である.
  6. (23 点) 追加の制約はない.

入力例 1

2
3 1
4 4

出力例 1

Yes
0
10
No

この入力例は Q = 2 個のシナリオからなる.

この出力例におけるシナリオ 1 の試合結果ではビーバー 1 がビーバー 2 に勝利し,ビーバー 2 がビーバー 3 に勝利し,ビーバー 3 がビーバー 1 に勝利した.したがって,3 匹のビーバー 1, 2, 3 は三すくみである.この他に 3 匹のビーバーを選ぶ方法はないので,三すくみとなるような 3 匹のビーバーの選び方はちょうど 1 通りである.

シナリオ 1 に対応する出力として,他に以下のようなものが考えられる.

Yes
1
01

シナリオ 2 では情報に合致する試合結果は存在しない.したがって,No と出力する.

この入力例は小課題 2, 3, 4, 5, 6 の制約を満たす.


入力例 2

1
5 3

出力例 2

Yes
0
11
001
0101

この出力例におけるシナリオ 1 の試合結果ではビーバー 1 がビーバー 4 に勝利し,ビーバー 4 がビーバー 3 に勝利し,ビーバー 3 がビーバー 1 に勝利した.したがって,3 匹のビーバー 1, 3, 4 は三すくみである.この他に三すくみとなるような 3 匹のビーバーの選び方として,ビーバー 2, 3, 4 を選ぶ方法とビーバー 3, 4, 5 を選ぶ方法がある.したがって,三すくみとなるような 3 匹のビーバーの選び方はちょうど 3 通りである.

この入力例はすべての小課題の制約を満たす.


Source Name

JOI 2023/2024 春季トレーニング Contest Day4 問題3