Hai đoạn tiếp theo của đề này và Juggle Struggle: Part 1 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. Nói cách khác, mỗi đoạn trong \(N\) đường tung hứng phải giao với cả \(N-1\) đoạn còn lại; các giao điểm không nhất thiết trùng nhau.

Sau vài sửa chữa vào phút chót, bạn có một cách bố trí mà mình cho là tráng lệ. Vì phải hoàn thành gấp, bạn muốn viết một trình kiểm tra xác định nó có thực sự tráng lệ hay không. Nếu không, đề bảo đảm có nhiều nhất 25 cặp nghệ sĩ không giao với mọi cặp khác. Trình kiểm tra phải báo danh sách tất cả những cặp đó để xem xét.

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à \(N\) dòng; dòng thứ \(i\) chứa bốn số nguyên \(X_i,Y_i,X'_i,Y'_i\). Hai điểm \((X_i,Y_i)\) và \((X'_i,Y'_i)\) là vị trí hai nghệ sĩ của cặp thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y. Nếu đầu vào là một cách bố trí tráng lệ, y là MAGNIFICENT. Nếu không, y là một danh sách số nguyên tăng nghiêm ngặt; chỉ số \(i\) xuất hiện trong danh sách khi và chỉ khi đường tung hứng của cặp thứ \(i\) không giao với ít nhất một đường tung hứng khác.

Ràng buộc

• \(-10^9\le X_i,Y_i,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í.
• Ngoại trừ nhiều nhất 25 cặp, đường tung hứng của mọi cặp giao với cả \(N-1\) đường còn lại.
• Có thể tồn tại hoặc không tồn tại một cách ghép lại các nghệ sĩ để tạo bố trí tráng lệ; đề không đưa ra bảo đảm về điều này.

Phân nhóm

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

Test Set 2 (Hidden): \(1\le T\le13\), \(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ụ

4
2
-1 -1 -1 1
1 1 1 -1
2
-1 -1 1 1
-1 1 1 -1
4
1 2 4 2
2 1 3 1
2 4 3 0
3 3 2 3
3
1 1 2 2
3 7 4 8
8 3 9 3

Case #1: 1 2
Case #2: MAGNIFICENT
Case #3: 1 2 4
Case #4: 1 2 3

Nguồn

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

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