Bạn được Công ty Xây dựng Hàng rào thuê làm nhân viên tạm thời và được giao hoàn thiện thiết kế hàng rào cho một cánh đồng. Mỗi hàng rào phải là một đoạn thẳng nối hai cọc. Mỗi cọc chiếm một điểm duy nhất và có vị trí cố định. Không có ba cọc nào thẳng hàng. Các hàng rào không được giao nhau, trừ trường hợp chúng gặp nhau tại đầu mút (các cọc).

Một người khác đã bắt đầu bản thiết kế nhưng bỏ dự án sau khi thêm đúng hai hàng rào. Bạn cần hoàn thiện thiết kế của họ. Để gây ấn tượng với cấp trên và khách hàng, bạn muốn thiết kế có nhiều hàng rào nhất có thể, bất kể độ dài của chúng.

Cho vị trí các cọc và những hàng rào đã dựng, hãy tìm cách thêm nhiều hàng rào nhất sao cho không có hai hàng rào nào (mới hoặc có sẵn) giao nhau, ngoại trừ có thể tại đầu mút (các cọc).

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên \(N\), số lượng cọc. Sau đó là \(N\) dòng; dòng thứ \(i\) chứa hai số nguyên \(X_i,Y_i\), là tọa độ X và Y của cọc thứ \(i\). Hai dòng cuối của mỗi bộ test mô tả hai hàng rào có sẵn. Mỗi dòng chứa hai số nguyên \(P_k,Q_k\), nghĩa là hàng rào có sẵn thứ \(k\) nối cọc thứ \(P_k\) và cọc thứ \(Q_k\) (các cọc được đánh số từ \(1\)).

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\)), còn \(y\) là số hàng rào lớn nhất có thể thêm vào thiết kế (không tính hai hàng rào có sẵn). Sau đó in thêm \(y\) dòng. Mỗi dòng chứa hai số nguyên phân biệt \(i,j\) (đều từ \(1\) đến \(N\)), biểu diễn một hàng rào riêng nối cọc thứ \(i\) và cọc thứ \(j\). Không có cặp nào trong \(y+2\) hàng rào (gồm cả hàng rào có sẵn và hàng rào bạn thêm) được chồng lấn, ngoại trừ có thể tại đầu mút.

Ràng buộc

• \(1\le T\le50\).
• \(-10^9\le X_i\le10^9\) và \(-10^9\le Y_i\le10^9\) với mọi \(i\).
• \((X_i,Y_i)\ne(X_j,Y_j)\) với mọi \(i\ne j\).
• \(1\le P_k<Q_k\le N\) với mọi \(k\).
• Hai hàng rào có sẵn không giao nhau, ngoại trừ có thể tại đầu mút.
• Không có ba cọc nào thẳng hàng.

Phân nhóm

Phân nhóm 1 (phản hồi hiện)

• \(4\le N\le100\).

Phân nhóm 2 (phản hồi ẩn)

• \(4\le N\le10^5\).

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

Ví dụ

2
4
0 0
0 1
1 1
1 0
1 2
3 4
5
0 0
0 1
1 1
1 0
2 3
1 2
3 5

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

Nguồn

Google Code Jam 2021, Vòng 3, bài Fence Design.

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