Cho lưới ô vuông kích thước , các hàng được đánh số từ đến từ trên xuống dưới, các cột được đánh số từ đến từ trái sang phải. Ô ở hàng cột là ô . Người ta tô các ô vuông bởi màu, mã màu được đánh số từ đến . Ký hiệu là số lượng các màu khác nhau được dùng để tô các ô trong cột . Ta gọi độ đa sắc của lưới là giá trị .
Cho phép hoán đổi màu của hai ô bất kỳ trên lưới. Mỗi phép hoán đổi được mô ta bởi bộ số nguyên cho biết hai ô và được hoán đổi màu cho nhau.
Yêu cầu: Hãy xác định một dãy các phép hoán đổi để đưa bảng màu về trạng thái có độ đa sắc nhỏ nhất.
Dữ liệu vào:
Dòng đầu chứa số là số bộ dữ liệu .
nhóm dòng tiếp theo, mỗi nhóm dòng mô ta một bộ dữ liệu theo khuôn dạng sau:
Dòng đầu tiên chứa hai số nguyên
Dòng thứ i trong số dòng tiếp theo chứa số nguyên mô ta dòng của bảng màu.
Dữ liệu ra:
Gồm nhóm dòng tương ứng với bộ dữ liệu ở đầu vào:
Dòng đầu ghi số nguyên là số phép hoán đổi cần thực hiện
dòng tiếp theo, mỗi dòng ghi số nguyên mô ta một phép hoán đổi.
Nếu có nhiều dãy phép hoán đổi thì chỉ cần ghi ra dãy phép hoán đổi bất kỳ.
