Đặc Trưng Quốc Gia

Đề bài

Mô tả

Bảng chữ cái Bookland gồm m ký tự, ký hiệu bằng các số nguyên dương từ 1 đến m. Mỗi ký tự có thể ở dạng nhỏ hoặc lớn; dạng lớn của ký tự x được viết là x. Theo cách mã hoá BSCII:

  • Các ký tự lớn được sắp xếp theo thứ tự tăng của số hiệu: 1<2<3<
  • Các ký tự nhỏ được sắp xếp theo thứ tự tăng của số hiệu: 1<2<3<
  • Mọi ký tự lớn đều nhỏ hơn mọi ký tự nhỏ. Ví dụ: 2<3, 2<3, nhưng 3<2.

Một dãy ký tự x1,x2,,xa không lớn hơn từ điển so với y1,y2,,yb nếu một trong hai điều kiện sau đúng:

  • abxi=yi với mọi 1ia (tức từ thứ nhất là tiền tố của từ thứ hai);
  • Tồn tại vị trí j (1jmin(a,b)) sao cho x1=y1,,xj1=yj1xj<yj (theo thứ tự đã định nghĩa).

Cho một dãy n từ gồm toàn ký tự nhỏ. Bạn được phép chọn một tập ký tự và viết hoa toàn bộ các xuất hiện của chúng trong tất cả các từ (mỗi ký tự chỉ có thể được "viết hoa toàn bộ" hoặc "không viết hoa toàn bộ" — không được viết hoa chỉ một số xuất hiện riêng lẻ). Hãy tìm một tập ký tự để sau khi viết hoa, dãy từ trở thành sắp xếp theo thứ tự từ điển, hoặc kết luận không tồn tại.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên nm (2n105, 1m105).
  • Mỗi dòng trong n dòng tiếp theo mô tả một từ: số đầu là độ dài li (1li), tiếp theo là li số nguyên — các ký tự của từ (mỗi ký tự thuộc [1,m]).
  • Tổng độ dài của tất cả các từ không vượt quá 105.

Dữ liệu ra

  • Nếu không tồn tại cách viết hoa hợp lệ, in một dòng No.
  • Ngược lại, in Yes ở dòng đầu, sau đó in k — số ký tự cần viết hoa — ở dòng thứ hai, và in k số nguyên phân biệt mô tả các ký tự đó ở dòng thứ ba. Không yêu cầu k nhỏ nhất; nếu có nhiều đáp án hợp lệ, in ra bất kỳ.

Ràng buộc

  • 2n105
  • 1m105
  • 1li, tổng li105
  • 1 mọi ký tự m

Ví dụ

Input Output Giải thích
4 3
1 2
1 1
3 1 3 2
2 1 1
Yes
2
2 3
Sau khi viết hoa ký tự 23, dãy trở thành 2, 1, 1 3 2, 1 1. Do 2<13<1, dãy đã sắp đúng.
6 5
2 1 2
2 1 2
3 1 2 3
2 1 5
2 4 4
2 4 4
Yes
0
Dãy đã sắp đúng nên không cần viết hoa ký tự nào.
4 3
4 3 2 2 1
3 1 1 3
3 2 3 3
2 3 1
No Không có tập viết hoa nào làm dãy sắp đúng.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0