Bessie có một bảng cộng kích thước \(N\times N\) (\(1\le N\le 1000\)), trong đó số nguyên ở ô thuộc hàng \(r\) và cột \(c\) là \(r+c\), với mọi \(1\le r,c\le N\). Ví dụ, với \(N=3\), bảng sẽ trông như sau:

2 3 4
3 4 5
4 5 6

Không may, Elsie đã lấy được bảng và hoán vị nó bằng cách thực hiện ba loại thao tác sau bao nhiêu lần tùy ý:

1. Hoán đổi hai hàng.
2. Hoán đổi hai cột.
3. Chọn hai giá trị \(a\) và \(b\) đều xuất hiện trong bảng, sau đó đồng thời đổi mọi lần xuất hiện của \(a\) thành \(b\) và mọi lần xuất hiện của \(b\) thành \(a\).

Elsie luôn thực hiện các thao tác theo thứ tự tăng dần của loại; nghĩa là trước tiên cô thực hiện tùy ý (có thể không lần nào) các thao tác loại \(1\), sau đó loại \(2\), và cuối cùng là loại \(3\).

Hãy giúp Bessie khôi phục một trạng thái khả dĩ của bảng sau khi Elsie đã thực hiện xong tất cả thao tác loại \(1\) và \(2\), nhưng trước khi thực hiện bất kỳ thao tác loại \(3\) nào. Có thể có nhiều đáp án, trong trường hợp đó bạn cần in đáp án nhỏ nhất theo thứ tự từ điển.

Để so sánh hai bảng theo thứ tự từ điển, hãy so sánh các phần tử đầu tiên mà chúng khác nhau khi đọc cả hai bảng theo thứ tự tự nhiên (các hàng từ trên xuống dưới, trong mỗi hàng từ trái sang phải).

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

\(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên, biểu diễn bảng cộng của Bessie sau khi Elsie đã hoán vị nó.

Dữ liệu ra

Trạng thái nhỏ nhất theo thứ tự từ điển có thể có của bảng sau tất cả thao tác loại \(1\) và \(2\), nhưng trước bất kỳ thao tác loại \(3\) nào. Đảm bảo đáp án tồn tại.

Ví dụ

1
2

2

3
3 4 2
5 2 3
6 3 5

4 2 3
5 3 4
6 4 5

2 3 4
3 4 5
4 5 6
-> (thao tác 1: hoán đổi cột 2 và 3)
2 4 3
3 5 4
4 6 5
-> (thao tác 1: hoán đổi cột 1 và 2)
4 2 3
5 3 4
6 4 5
-> (thao tác 3: hoán đổi giá trị 2 và 3)
4 3 2
5 2 4
6 4 5
-> (thao tác 3: hoán đổi giá trị 3 và 4)
3 4 2
5 2 3
6 3 5

4 6 5
3 5 4
2 4 3

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

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

Phân nhóm

• Inputs 4-5: \(N\le 6\).
• Inputs 6-7: \(N\le 8\).
• Inputs 8-11: \(N\le 100\).
• Inputs 12-15: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Silver — Table Recovery

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1472

Tác giả đề: Benjamin Qi