THỰC HÀNH

Cho một bàn cờ hình vuông kích thước N×N được chia thành N dòng đánh số từ 1 đến N, N cột đánh số từ 1 đến N. Bạn được phép đặt một con mã ở một ô bất kỳ trên bàn cờ, hãy tìm tìm một hành trình của quân ma đi qua tất cả các ô của bàn cờ, mỗi ô đúng một lần (theo đúng luật đi của quân mã).

Dữ liệu vào:

Một số nguyên dương N là kích thước bàn cờ (biết rằng với kích thước bàn cờ này thì luôn tìm được vị trí đặt quân mã và hành trình đi hết bà cờ).

Dữ liệu ra:

Gồm N×N dòng, mỗi dòng là một cặp số nguyên dương là tọa độ dòng và cột của quân mã đi qua (theo đúng thứ tự trong hành trình).

Ví dụ:

Dữ liệu vào:
5
Dữ liệu ra:
1 3
2 5
4 4
5 2
3 1
1 2
2 4
4 5
5 3
4 1
3 3
2 1
4 2
5 4
3 5
1 4
2 2
4 3
5 5
3 4
1 5
2 3
1 1
3 2
5 1

Giới hạn: 5 ≤ n ≤ 30.