Bạn là phóng viên tại sự kiện "Excellent Glutenous Ovenmasters of Italy", nơi \(N\) thợ làm pizza giỏi nhất nước Ý vừa tranh tài. Mỗi người làm một chiếc pizza. Ban giám khảo xếp hạng các pizza bằng các số phân biệt từ \(0\) (tốt nhất) đến \(N-1\) (tệ nhất); mỗi thợ nhận thứ hạng của chiếc pizza mình làm.

Sau cuộc thi, tất cả thợ mang pizza đến buổi tiệc. Họ đến lần lượt theo một thứ tự chưa biết. Có \(M\) bàn, đánh số từ \(0\) đến \(M-1\). \(M\) người đến đầu tiên đặt pizza lên lần lượt các bàn \(0,1,\ldots,M-1\).

Mỗi người đến sau muốn ăn một chiếc pizza ngon hơn pizza của mình, nhưng không ngon hơn quá mức cần thiết. Cụ thể, họ chọn pizza đang có thứ hạng lớn nhất trong số các thứ hạng vẫn nhỏ hơn thứ hạng của mình. Họ ăn hết pizza đó rồi để pizza của mình lại trên cùng bàn. Nếu không có pizza phù hợp, người đó thất vọng rời đi và mang pizza của mình theo.

Ví dụ 1 có \(M=2\) bàn và thứ tự đến là \(1,0,3,5,4,2\).

Hình 1: Hai thợ đầu tiên đặt pizza lên các bàn trống \(0\) và \(1\) theo thứ tự đến.

Hình 2: Sau khi các bàn đã có pizza, mỗi thợ chọn chiếc pizza tệ nhất nhưng vẫn ngon hơn pizza của mình; thợ rời đi nếu không có lựa chọn phù hợp.

Sau buổi tiệc, trên mỗi bàn còn một chồng khay theo đúng thứ tự các pizza đã được phục vụ tại bàn đó, từ dưới lên trên. Từ các chồng khay này, hãy khôi phục thứ tự các thợ đã đến. Nếu có nhiều thứ tự hợp lệ, để đạt trọn điểm phải in thứ tự nhỏ nhất theo thứ tự từ điển.

Hình 3: Các chồng khay của ví dụ 1, theo thứ tự từ lần đến đầu tiên ở dưới lên lần gần nhất ở trên; khay tô nổi chứa pizza còn lại cuối buổi tiệc.

Dãy \(a\) nhỏ hơn dãy \(b\) theo thứ tự từ điển nếu tồn tại vị trí \(t\) sao cho \(a_i=b_i\) với mọi \(i<t\) và \(a_t<b_t\).

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N,M\).

\(M\) dòng tiếp theo mô tả các chồng khay. Dòng \(i\) bắt đầu bằng \(T_i\), sau đó là \(T_i\) số \(b_{i,0},b_{i,1},\ldots,b_{i,T_i-1}\), là thứ hạng các pizza đã được phục vụ tại bàn \(i\), theo thứ tự từ khay dưới cùng (đến trước) lên khay trên cùng (đến sau).

Dữ liệu ra

In NO nếu không có thứ tự nào phù hợp.

Nếu có, in YES, rồi in một dòng gồm hoán vị \(a_0,a_1,\ldots,a_{N-1}\) của các thứ hạng theo thứ tự đến. Nếu có nhiều đáp án, hãy in đáp án nhỏ nhất theo thứ tự từ điển. Các đáp án đúng một phần vẫn có thể nhận điểm như mô tả dưới đây.

Ràng buộc

• \(1\le M\le N\le300\,000\).
• \(0\le b_{i,j}\le N-1\).
• Tất cả \(b_{i,j}\) đôi một khác nhau.
• \(1\le T_i\le N\).

Cách chấm điểm đầu ra

• Chỉ in đúng dòng đầu YES/NO: nhận \(20\%\) số điểm của test.
• In đúng dòng đầu và một thứ tự hợp lệ khi đáp án là YES, nhưng chưa chắc nhỏ nhất theo thứ tự từ điển: nhận thêm \(20\%\).
• Để nhận \(60\%\) còn lại, khi đáp án là YES phải in đúng thứ tự hợp lệ nhỏ nhất theo thứ tự từ điển.

Phân nhóm

1. \(20\) điểm: \(M=1\).
2. \(10\) điểm: \(M=2\), \(N\le200\) và \(\sum T_i=N\).
3. \(20\) điểm: \(M\le N\le200\) và \(\sum T_i=N\).
4. \(20\) điểm: \(M\le10\).
5. \(30\) điểm: không có ràng buộc thêm.

Ví dụ

6 2
3 1 3 5
2 0 4

YES
1 0 3 5 4 2

6 2
3 1 3 4
2 0 2

NO

4 2
2 0 3
2 1 2

NO

3 1
2 0 2

YES
0 2 1

8 1
8 7 6 5 4 3 2 1 0

NO

12 4
3 2 3 4
1 5
1 6
5 7 8 9 10 11

YES
2 5 6 7 0 1 3 4 8 9 10 11

Nguồn

EGOI 2026 - Ngày 1, Ovenmasters.

Đề bài EGOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).