Khi một lập trình viên thi đấu nghĩ về một cái cây, đó không phải là cùng một cái cây mà một người bình thường nghĩ đến. May mắn thay, trong nhiệm vụ này, cả hai ý nghĩa đều đúng.

Nikola yêu thiên nhiên và thường đi dạo trong rừng, ngắm nhìn các cây cối và ngưỡng mộ kích thước, bậc nút, sự ngẫu nhiên có quy luật của chúng, v.v. Trong ngày mùa xuân tuyệt đẹp này, có thêm nhiều lý do để nhìn lên những sinh vật tuyệt vời này: cây cối đầy màu sắc và điều đó đã thu hút sự chú ý của Nikola.

Vì vậy, một ngày nọ, anh đã quan sát một cây lớn với N nút, nhìn thấy một màu sắc ở mỗi nút. Đó là một bông hoa, một con vật, hay Nikola đơn giản là đã trở nên điên rồ, khó mà nói được. Nhưng anh đã nhìn vào cây đó rất lâu, và trong một ma trận ~N \times N~, anh đã viết, cho mỗi hai nút, số lượng màu sắc khác nhau trên một đường đi đơn giản duy nhất giữa (và bao gồm) hai nút này. Đáng tiếc, khi chiêm ngưỡng tất cả những màu sắc đó, Nikola hoàn toàn quên mất cây trông như thế nào và màu sắc nào ở các nút.

Vì vậy, anh cần sự giúp đỡ của bạn. Từ ma trận anh viết, xác định một cây có thể và màu sắc có thể của các nút tương ứng. Màu sắc nên được biểu thị bằng các số từ ~1, 2, …, N~. Đảm bảo rằng Nikola không mắc sai lầm; nói cách khác, một giải pháp sẽ tồn tại.

Input

• Dòng đầu tiên chứa một số phụ tác vụ ~1, 2~ hoặc ~3~ từ phần Điểm số dưới đây.
• Dòng thứ hai chứa một số nguyên ~N~ ~(1 \leq N \leq 3000)~, số lượng nút trong cây, được biểu thị bằng ~1, 2, ..., N~.
• Mỗi dòng trong ~N~ dòng tiếp theo chứa ~N~ số nguyên, trong đó số thứ ~j~ trong dòng thứ ~i~ bằng số lượng màu sắc khác nhau trên đường đi từ nút ~i~ đến nút ~j~.

Output

• Dòng đầu tiên nên chứa ~N~ số nguyên cách nhau bởi khoảng trắng giữa ~1~ và ~N~: màu sắc của các nút ~1, 2, ..., N~.
• Mỗi dòng trong ~N – 1~ dòng tiếp theo nên chứa hai số nguyên ~A, B~ biểu thị cạnh (các nút lân cận) trong cây. Thứ tự của các cạnh và nút trong một cạnh là tùy ý.

Chú ý

• ~18 \%~ điểm thỏa mãn các số trong ma trận đều bằng ~1~ hoặc ~2~.
• ~25 \%~ điểm thỏa mãn có một giải pháp trong đó cây là một chuỗi các nút ~1, 2, ..., N~ theo thứ tự đó, tức là các cạnh là ~(i, i + 1)~ cho mỗi ~i = 1, ..., N – 1~.

Sample Input 1

3
5
1 2 2 2 3
2 1 3 3 2
2 3 1 3 4
2 3 3 1 3
3 2 4 3 1

Sample Output 1

1 2 3 4 4
1 2
1 3
1 4
2 5

Sample Input 2

2
4
1 2 3 3
2 1 2 2
3 2 1 2
3 2 2 1

Sample Output 2

1 2 3 2
1 2
2 3
3 4

Sample Input 3

1
5
1 2 2 2 2
2 1 1 2 2
2 1 1 2 2
2 2 2 1 2
2 2 2 2 1

Sample Output 3

1 2 2 1 2
1 2
2 3
2 4
1 5