Mr. Jolly dạy bóng đá cho \(N\) đứa trẻ được đánh số từ \(1\) đến \(N\). Ông thường để lại trên sân nơi thi đấu một viên kẹo cho mỗi trẻ. Khi trận đấu kết thúc, mỗi trẻ có thể lấy và ăn một viên kẹo làm phần thưởng.

Sau trận đấu, bọn trẻ đều mệt nên mỗi em muốn lấy viên kẹo gần mình nhất theo khoảng cách Euclid. Điều này có thể gây tranh giành nếu cùng một viên kẹo gần nhất với từ hai trẻ trở lên. Để tránh chuyện đó, sau trận đấu tất cả trẻ đứng yên tại chỗ, còn Mr. Jolly lần lượt gọi tên từng em. Khi được gọi, trẻ lấy viên kẹo gần mình nhất trong số những viên chưa bị lấy. Nếu có nhiều viên đồng hạng ở khoảng cách nhỏ nhất, Mr. Jolly được quyết định trẻ sẽ lấy viên nào.

Cách làm này đã hoạt động rất tốt trong một thời gian, nhưng hôm nay tai họa xảy ra: khi bày kẹo, Mr. Jolly vô tình làm rơi viên thạch việt quất ông định ăn sau khi bọn trẻ về nhà. Trên sân giờ có \(N\) trẻ và \(N+1\) viên kẹo. Các viên được đánh số từ \(1\) đến \(N+1\), trong đó viên số \(1\) là thạch việt quất của Mr. Jolly. Liệu ông có thể cứu viên thạch bằng cách gọi tên bọn trẻ theo một thứ tự sao cho thạch việt quất là viên duy nhất còn lại hay không?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa \(N\), số trẻ trên sân. \(N\) dòng tiếp theo mô tả vị trí của các trẻ; mỗi dòng chứa hai số nguyên \(X_i,Y_i\), là vị trí của trẻ thứ \(i\) sau trận đấu. Sau đó là \(N+1\) dòng mô tả vị trí các viên kẹo, trong đó viên đầu tiên là thạch việt quất của Mr. Jolly. Mỗi dòng chứa hai số nguyên \(X_j,Y_j\), là vị trí viên kẹo thứ \(j\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ \(1\). Nếu không có cách chọn thứ tự trẻ và phá hòa để thạch việt quất không bị ăn, \(y\) là IMPOSSIBLE. Nếu cứu được viên thạch, \(y\) là POSSIBLE.

Trong trường hợp POSSIBLE, in thêm \(N\) dòng biểu diễn thứ tự các trẻ đi lấy kẹo và viên kẹo mỗi trẻ lấy. Dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\), nghĩa là trẻ \(A_i\) đi tiếp theo và lấy viên \(B_i\). Tại thời điểm đó, \(B_i\) phải là viên gần nhất hoặc đồng hạng gần nhất với trẻ \(A_i\).

Ràng buộc

• \(1\le T\le100\).
• \(-10^9\le X_i,Y_i\le10^9\) với mọi trẻ \(i\).
• \(-10^9\le X_j,Y_j\le10^9\) với mọi viên kẹo \(j\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(1\le N\le10\).
• Test Set 2 (phán quyết ẩn): \(1\le N\le1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
2
-3 0
-1 0
3 0
-2 -1
-2 1
1
0 0
1 1
2 2
3
10 0
-10 0
0 0
0 5
-1 0
5 0
0 -5
2
3 4
3 4
5 7
3 4
5 7

Case #1: POSSIBLE
2 2
1 3
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
3 2
2 4
1 3
Case #4: POSSIBLE
1 2
2 3

Nguồn

Google Code Jam 2022, Vòng 2, bài Saving the Jelly.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.