Hai đoạn tiếp theo của đề này và Juggle Struggle: Part 2 giống hệt nhau. Ngoài phần đó, hai bài có thể giải độc lập; bạn không cần đọc hay giải bài này để đọc hoặc giải bài kia.

Là quản lý nhóm Graceful Chainsaw Jugglers, bạn quyết định làm tiết mục hấp dẫn hơn. Thay vì mỗi nghệ sĩ tự tung hứng cưa máy của mình, bạn muốn họ ghép thành cặp, mỗi cặp ném cưa máy qua lại cho nhau.

Trong tiết mục mới, \(2N\) nghệ sĩ cùng đứng trên sân khấu, được chia thành \(N\) cặp, mỗi người thuộc đúng một cặp.

Bạn cho rằng tiết mục sẽ ấn tượng hơn nếu cưa máy của các cặp khác nhau có nguy cơ va chạm. Xem sân khấu là một mặt phẳng hai chiều; đoạn thẳng nối vị trí hai nghệ sĩ trong một cặp gọi là đường tung hứng của cặp. Khi hai đường tung hứng giao nhau, ta nói cưa máy của hai cặp có nguy cơ va chạm. Vị trí không gian và cách ghép cặp tạo thành một cách bố trí. Cách bố trí là tráng lệ nếu đường tung hứng của mọi hai cặp đều giao nhau.

Sau rất nhiều suy nghĩ và thiết kế, bạn đã tìm được một cách bố trí tráng lệ và ghi vị trí cùng cách ghép cặp lên giấy. Không may, một cú ném cưa tệ đã cắt đôi tờ giấy và bạn làm mất nửa ghi các cặp.

Đồ trang trí sân khấu đã được thiết kế theo vị trí các nghệ sĩ nên không thể thay đổi. Buổi ra mắt được mong đợi chỉ còn vài giờ nữa; hãy tìm một cách bố trí tráng lệ. Cho vị trí mọi nghệ sĩ trên sân khấu hai chiều, hãy ghép họ thành các cặp sao cho bố trí tráng lệ.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng số nguyên \(N\), số cặp nghệ sĩ. Tiếp theo là \(2N\) dòng; dòng thứ \(i\) chứa hai số nguyên \(X_i,Y_i\), tọa độ vị trí nghệ sĩ thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: j1 j2 ... j(2N), biểu thị nghệ sĩ \(i\) ghép với nghệ sĩ \(j_i\) với mọi \(i\). Phải có \(j_{j_i}=i\) với mọi \(i\).

Ràng buộc

• \(-10^9\le X_i,Y_i\le10^9\) với mọi \(i\).
• Không có ba vị trí nghệ sĩ thẳng hàng; điều này cũng kéo theo không có hai người cùng vị trí.
• Luôn tồn tại ít nhất một cách ghép tạo nên bố trí tráng lệ.

Phân nhóm

Test Set 1 (Visible): \(1\le T\le100\), \(2\le N\le100\).

Test Set 2 (Hidden): \(1\le T\le10\), \(2\le N\le10^5\).

Đ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ụ

3
2
-1 -1
-1 1
1 1
1 -1
3
1 2
2 1
2 3
3 1
3 3
4 2
3
7 1
1 1
7 2
5 5
3 5
1 2

Case #1: 3 4 1 2
Case #2: 6 5 4 3 2 1
Case #3: 5 4 6 2 1 3

Nguồn

Google Code Jam 2019, Chung kết thế giới, bài Juggle Struggle: Part 1.

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