Một giải bóng bàn được tổ chức ở vương quốc JOI với \(N\) chú hải ly, được đánh số từ \(1\) đến \(N\). Giải đấu diễn ra theo thể thức vòng tròn: mỗi cặp đấu với nhau một trận.

Bitaro cho bạn biết các thông tin sau về kết quả giải đấu:

• Không có trận hòa.
• Có đúng \(M\) cách chọn ba chú hải ly tạo thành một vòng thắng thua. Cụ thể, ba chú hải ly \(i,j,k\) \((1 \le i<j<k \le N)\) tạo thành một vòng thắng thua khi đúng một trong hai điều sau xảy ra: \(i\) thắng \(j\), \(j\) thắng \(k\), \(k\) thắng \(i\); hoặc \(i\) thắng \(k\), \(k\) thắng \(j\), \(j\) thắng \(i\).

Bạn không biết thông tin của Bitaro có chính xác hay không. Hãy xác định có tồn tại kết quả giải đấu phù hợp với thông tin đó hay không; nếu có, hãy tìm một kết quả như vậy.

Dữ liệu vào

Một bộ dữ liệu gồm \(Q\) tình huống, được đánh số từ \(1\) đến \(Q\). Mỗi tình huống cho biết số hải ly tham gia \(N\) và số bộ ba tạo thành vòng thắng thua \(M\).

Đọc từ đầu vào chuẩn theo định dạng:

Q
N_1 M_1
N_2 M_2
...
N_Q M_Q

Cặp \(N_i,M_i\) là các giá trị \(N,M\) của tình huống thứ \(i\).

Dữ liệu ra

In đáp án cho các tình huống theo thứ tự từ \(1\) đến \(Q\).

Nếu tồn tại một kết quả phù hợp, in:

Yes
S_2
S_3
...
S_N

Với mỗi \(2 \le i \le N\), \(S_i\) là xâu độ dài \(i-1\) chỉ gồm 0 và 1. Ký tự thứ \(j\) \((1 \le j<i)\) của \(S_i\) là 0 nếu hải ly \(i\) thua hải ly \(j\), và là 1 nếu hải ly \(i\) thắng hải ly \(j\). Nếu có nhiều kết quả phù hợp, có thể in bất kỳ kết quả nào.

Nếu không tồn tại kết quả phù hợp, in No cho tình huống đó.

Ràng buộc

• \(Q \ge 1\).
• Trong mỗi tình huống, \(3 \le N \le 5\,000\).
• Trong mỗi tình huống, \(0 \le M \le \dfrac{N(N-1)(N-2)}{6}\).
• Tổng các giá trị \(N\) của \(Q\) tình huống không vượt quá \(5\,000\).
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (5 điểm): \(M \le N-2\) trong mọi tình huống.
• Nhóm 2 (4 điểm): Tổng các giá trị \(N\) không vượt quá \(7\).
• Nhóm 3 (23 điểm): Tổng các giá trị \(N\) không vượt quá \(20\).
• Nhóm 4 (30 điểm): Tổng các giá trị \(N\) không vượt quá \(150\).
• Nhóm 5 (15 điểm): Tổng các giá trị \(N\) không vượt quá \(600\).
• Nhóm 6 (23 điểm): Không có ràng buộc bổ sung.

Ví dụ

2
3 1
4 4

Yes
0
10
No

Yes
1
01

1
5 3

Yes
0
11
001
0101

Nguồn

JOI 2023/2024, kỳ thi tuyển chọn mùa xuân, ngày thi thứ tư (24/03/2024). Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.