Trilobite rất thích xây dựng tàu điện ngầm. Anh ấy đã thiết kế $n$ tuyến đường, mỗi tuyến đường có $n+1$ địa điểm xây dựng trạm, được biểu diễn bằng tọa độ trên mặt phẳng.
Để làm phong phú trải nghiệm tàu điện ngầm, Trilobite quyết định mỗi tuyến đường sẽ là một đoạn thẳng! Nghĩa là, đối với mỗi tuyến đường, Trilobite chỉ chọn hai trạm và nối một đoạn thẳng giữa hai trạm đó. Để tối đa hóa sự phiền toái cho hành khách khi chuyển tuyến, Trilobite yêu cầu số lượng giao điểm giữa $n$ tuyến đường tàu điện ngầm được xây dựng phải là ít nhất. Lưu ý rằng giao điểm bao gồm cả các điểm đầu và điểm cuối. Hãy lập kế hoạch cho một phương án hợp lệ.
Nói cách khác: Cho $n$ loại điểm trên mặt phẳng, mỗi loại có $n+1$ điểm. Yêu cầu chọn ra hai điểm khác nhau trong mỗi loại để nối thành một đoạn thẳng, sao cho tổng số giao điểm giữa $n$ đoạn thẳng là ít nhất. Hãy xuất ra phương án xây dựng.
Lưu ý: Nếu hai đoạn thẳng cùng nằm trên một đường thẳng, số lượng giao điểm được định nghĩa là vô cùng. Tất cả các giá trị vô cùng được coi là bằng nhau.
Dữ liệu vào
Bài toán này có nhiều bộ dữ liệu thử nghiệm. Dòng đầu tiên chứa một số nguyên dương $T$ là số lượng bộ dữ liệu. Đối với mỗi bộ dữ liệu:
Dòng đầu tiên chứa một số nguyên dương $n$ là số lượng tuyến đường.
$n$ dòng tiếp theo, mỗi dòng chứa $2n+2$ số nguyên, trong đó số nguyên thứ $2i-1$ và $2i$ là tọa độ $(x_i, y_i)$ của một trạm thuộc tuyến đường hiện tại, và nhãn của trạm đó là $i$.
Đảm bảo rằng tất cả các tọa độ trạm đều khác nhau.
Dữ liệu ra
Đối với mỗi bộ dữ liệu, xuất ra $n$ dòng, mỗi dòng chứa hai số nguyên dương, lần lượt biểu thị nhãn của hai trạm được kết nối bởi mỗi tuyến đường. Bạn chỉ cần xuất ra một phương án bất kỳ.
Ví dụ
Dữ liệu vào 1
1 2 5 0 0 8 10 8 0 4 10 4 5 12
Dữ liệu ra 1
1 3 1 3
Ghi chú
Trong hình, các điểm màu xanh dương và màu đỏ lần lượt biểu thị các trạm của tuyến đường số 1 và số 2, đường màu xanh và đường màu đỏ lần lượt biểu thị các đoạn thẳng được chọn cho tuyến đường số 1 và số 2.
Lưu ý rằng bạn chỉ cần xuất ra một phương án bất kỳ, ví dụ:
1 2 2 3
cũng là một đáp án đúng.
Giới hạn
| Nhiệm vụ con | Điểm | Giới hạn bổ sung |
|---|---|---|
| 1 | 30 | $n\le 5,\sum n\le 50$ |
| 2 | 20 | Tồn tại một cách sắp xếp $n(n+1)$ điểm sao cho tọa độ của điểm thứ $i$ chính xác là $(i,i)$ |
| 3 | 20 | $n\leq 100$ |
| 4 | 30 | Không có |
Đối với tất cả dữ liệu: $1\le n\le1000,\sum n\leq 2000$, $|x_i|,|y_i|\le10^9$.