Vùng Hạ Long có hòn đảo được đánh số từ đến . Tọa độ hòn đảo thứ trên mặt phẳng tọa độ được cho bởi cặp số . Trên mỗi đảo có bể chứa xăng có khả năng cung cấp đầy các thiết bị chứa xăng của ca nô. Biết rằng các thiết bị chứa xăng của ca nô không thể chứa đủ số xăng đi hết km.
Hãy tìm một hành trình cho ca nô đi từ một đảo đến đảo mà số lần ghé vào các đảo để lấy xăng là nhỏ nhất.
Dữ liệu vào:
Dòng đầu ghi số nguyên dương ;
Các dòng tiếp theo, dòng chứa hai số nguyên và là tọa độ đảo thứ .
Dữ liệu ra:
Nếu có đường đi thì dòng đầu tiên ghi số đảo ghé vào lấy xăng (trừ và ), dòng thứ hai ghi số hiệu các đảo theo thứ tự của hành trình. Nếu không có đường đi thì ghi .
