Thu gom đồ vật

Một chiếc túi được đặt tại điểm $(x_s,y_s)$ trên mặt phẳng toạ độ, và có $n$ đồ vật nằm rải rác xung quanh. Ban đầu bạn đứng ngay tại vị trí chiếc túi.

Bạn không thể di chuyển chiếc túi, và mỗi lần chỉ mang được tối đa $2$ đồ vật. Ngoài ra, một khi đã nhặt một đồ vật lên thì bạn bắt buộc phải mang nó về túi, không được đặt nó xuống ở bất kỳ chỗ nào khác. Vì vậy mỗi lượt đi có đúng một trong hai dạng: từ túi tới một đồ vật rồi quay về túi, hoặc từ túi tới một đồ vật, sang một đồ vật khác, rồi quay về túi.

Thời gian di chuyển giữa hai điểm bằng bình phương độ dài đoạn thẳng nối hai điểm đó. Hãy tìm cách thu gom toàn bộ $n$ đồ vật vào túi sao cho tổng thời gian là nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $x_s$, $y_s$ là toạ độ chiếc túi.
• Dòng thứ hai chứa số nguyên $n$ là số đồ vật.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên là toạ độ của đồ vật thứ $i$.

Dữ liệu ra

• Dòng đầu in ra tổng thời gian nhỏ nhất.
• Dòng thứ hai in ra một hành trình tối ưu: dãy các số trong đó $0$ là chiếc túi và $1..n$ là chỉ số đồ vật. Hành trình phải bắt đầu và kết thúc tại $0$, mỗi đồ vật xuất hiện đúng một lần, và giữa hai số $0$ liên tiếp có $1$ hoặc $2$ đồ vật.

Nếu có nhiều hành trình tối ưu, in ra hành trình nào cũng được.

Ràng buộc

• $1\le n\le 24$
• Mọi toạ độ là số nguyên và không vượt quá $100$ về giá trị tuyệt đối.
• Tất cả các vị trí đã cho (kể cả chiếc túi) đôi một khác nhau.

Ví dụ