Cho một DFA đầy đủ với tập trạng thái chấp nhận F. DFA bù nhận cùng bảng chuyển nhưng đảo tập chấp nhận: mọi trạng thái không thuộc F trở thành chấp nhận và ngược lại (nhờ đó nó chấp nhận đúng phần bù của ngôn ngữ). Hãy in ra tập trạng thái chấp nhận của DFA bù.
Bảng chữ cái gồm k ký tự đầu tiên: a, b, c, … (chỉ số j ứng với ký tự chr(97+j)).
Ví dụ:
Input:
3 2
1 0
2 0
2 2
0
1 2
Output:
2
0 1
Khối mô tả DFA gồm:
n k — số trạng thái (đánh số 0..n-1) và kích thước bảng chữ cái.n dòng tiếp theo: dòng i gồm k số, số thứ j là trạng thái đích khi ở trạng thái i đọc ký tự thứ j.s.f rồi f số — tập trạng thái chấp nhận (nếu f=0 chỉ có số 0).1 ≤ n ≤ 10^5, 1 ≤ k ≤ 26.
In dòng 1: số lượng trạng thái chấp nhận của DFA bù. Dòng 2: các trạng thái đó theo thứ tự tăng dần, cách nhau một dấu cách (dòng trống nếu không có).
Ví dụ:
Đầu vào:
3 2
1 0
2 0
2 2
0
1 2
Đầu ra:
2
0 1
Giải thích:
Đang tải editor...