Kỹ thuật nhảy rất quan trọng đối với ninja. Một nhóm ninja sẽ luyện nhảy trên một hồ lớn.

Trong hồ có \(N\) tảng đá, được đánh số từ \(1\) đến \(N\). Vị trí mỗi tảng đá được xem như một điểm trên mặt phẳng tọa độ hai chiều. Tảng đá thứ \(i\) ở tọa độ \((X_i,Y_i)\).

Các ninja muốn tìm một lộ trình nhảy từ tảng đá này sang tảng đá khác, đi qua mỗi tảng đá đúng một lần, rồi quay lại tảng đá xuất phát sau khi đã đi qua tất cả \(N\) tảng đá. Mỗi bước nhảy là đoạn thẳng nối hai tảng đá.

Để bảo đảm an toàn, lộ trình không được tự cắt. Nói cách khác, khi nhìn hồ từ trên cao, lộ trình không được đi qua cùng một vị trí nhiều lần, ngoại trừ việc quay lại điểm xuất phát để khép kín lộ trình.

Yêu cầu

Cho vị trí của \(N\) tảng đá, hãy tìm một lộ trình thỏa mãn các điều kiện trên, hoặc xác định rằng không tồn tại lộ trình như vậy.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(N\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(X_i,Y_i\), phân cách bởi dấu cách, là tọa độ tảng đá thứ \(i\).

Không có hai tảng đá ở cùng một vị trí.

Dữ liệu ra

Nếu có lộ trình hợp lệ, ghi ra đầu ra chuẩn \(N\) dòng. Dòng thứ \(j\) chứa số hiệu tảng đá thứ \(j\) được ghé thăm trong lộ trình. Sau tảng đá được ghi ở dòng cuối, lộ trình quay lại tảng đá được ghi ở dòng đầu; không ghi lại tảng đá xuất phát ở cuối đầu ra. Nếu có nhiều lộ trình hợp lệ, có thể in ra bất kỳ lộ trình nào.

Nếu không tồn tại lộ trình hợp lệ, chỉ in một dòng chứa số 0.

Ràng buộc

• \(3\le N\le100\,000\).
• \(0\le X_i\le1\,000\,000\,000\) với mọi \(1\le i\le N\).
• \(0\le Y_i\le1\,000\,000\,000\) với mọi \(1\le i\le N\).
• Các cặp tọa độ \((X_i,Y_i)\) đôi một khác nhau.
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

• \(10\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le8\).
• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le16\).
• \(50\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le1000\).

Ví dụ

12
0 0
0 10
0 20
10 0
10 10
10 20
20 0
20 10
20 20
30 0
30 10
30 20

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

3
23 7
91 27
40 12

0