Cho hoán vị \(A=[A_1,\ldots,A_N]\) và dãy \(B=[B_1,\ldots,B_M]\) có các phần tử khác nhau. Ban đầu \(X=A\). Có thể lặp lại hai thao tác: đổi chỗ hai phần tử kề nhau \(X_i<X_{i+1}\), hoặc gộp hai phần tử kề nhau thành \(\min(X_i,X_{i+1})\).

Hãy quyết định có thể biến \(X\) thành \(B\) không. Nếu có, in bất kỳ dãy thao tác hợp lệ nào; không cần tối thiểu số thao tác.

Dữ liệu vào

• Dòng đầu: \(N\), \(M\).
• Dòng thứ hai: dãy \(A\).
• Dòng thứ ba: dãy \(B\).

Dữ liệu ra

In NO nếu không thể. Nếu có thể, in YES, số thao tác \(Q\) (\(0\le Q\le N^2\)), rồi \(Q\) dòng thao tác theo thứ tự thực hiện: 1 i để đổi chỗ hoặc 2 i để gộp vị trí \(i\) và \(i+1\). Mỗi chỉ số phải hợp lệ đối với độ dài hiện tại của \(X\); thao tác loại 1 còn đòi hỏi \(X_i<X_{i+1}\). Sau mọi thao tác, \(X\) phải bằng đúng \(B\).

Ràng buộc

• \(1\le M\le N\le3000\).
• \(A\) là hoán vị của \(1,\ldots,N\).
• \(1\le B_i\le N\) với mọi \(1\le i\le M\), và các phần tử của \(B\) đôi một khác nhau.

Phân nhóm

• Nhóm 1 (7 điểm): \(N\le8\).
• Nhóm 2 (8 điểm): \(M=1\).
• Nhóm 3 (12 điểm): \(M=N\).
• Nhóm 4 (10 điểm): \(A_i=i\).
• Nhóm 5 (13 điểm): \(M=N-1\).
• Nhóm 6 (15 điểm): \(B\) là dãy con của \(A\).
• Nhóm 7 (30 điểm): \(N\le300\).
• Nhóm 8 (5 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 2
1 4 2 3
3 1

YES
6
1 1
1 2
1 3
2 1
1 1
2 2

Sáu thao tác trên lần lượt biến đổi

nên kết quả đúng bằng \(B\).

2 1
1 2
2

NO

4 4
3 2 1 4
3 1 2 4

NO

4 2
1 3 2 4
1 3

NO

Nguồn

KOI 2026 Round 2, problem Sequence Operations. Tài liệu, dữ liệu chấm và mã nguồn mẫu từ Korean Olympiad in Informatics, phát hành theo CC BY-NC-SA 4.0.